#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <strings.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <getopt.h>
#include <errno.h>
#include <limits.h>  /* for CHAR_BIT */
#include <assert.h>


#define BUF 512
#define DEX_MAGIC       "dex\n"
#define DEX_OPT_MAGIC   "dey\n"
#define DEX_MAGIC_VERS  "036\0"
#define DEX_OPT_MAGIC_VERS  "036\0"
#define DEX_MAGIC_VERS_API_13  "035\0"

#define local static
#define SHA1HANDSOFF
#define HASHSIZE 20

#define BASE 65521      /* largest prime smaller than 65536 */
#define NMAX 5552
#define Z_NULL	0

typedef unsigned long int uLong;
typedef unsigned int uInt;
typedef unsigned char Byte;
typedef Byte Bytef;

#define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
#define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
#define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
#define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
#define DO16(buf)   DO8(buf,0); DO8(buf,8);

#ifdef NO_DIVIDE
/* note that this assumes BASE is 65521, where 65536 % 65521 == 15
   (thank you to John Reiser for pointing this out) */
#  define CHOP(a) \
    do { \
        unsigned long tmp = a >> 16; \
        a &= 0xffffUL; \
        a += (tmp << 4) - tmp; \
    } while (0)
#  define MOD28(a) \
    do { \
        CHOP(a); \
        if (a >= BASE) a -= BASE; \
    } while (0)
#  define MOD(a) \
    do { \
        CHOP(a); \
        MOD28(a); \
    } while (0)
#  define MOD63(a) \
    do { /* this assumes a is not negative */ \
        z_off64_t tmp = a >> 32; \
        a &= 0xffffffffL; \
        a += (tmp << 8) - (tmp << 5) + tmp; \
        tmp = a >> 16; \
        a &= 0xffffL; \
        a += (tmp << 4) - tmp; \
        tmp = a >> 16; \
        a &= 0xffffL; \
        a += (tmp << 4) - tmp; \
        if (a >= BASE) a -= BASE; \
    } while (0)
#else
#  define MOD(a) a %= BASE
#  define MOD28(a) a %= BASE
#  define MOD63(a) a %= BASE
#endif

uLong adler32(
    uLong adler,
    const Bytef *buf,
    uInt len)
{
    unsigned long sum2;
    unsigned n;

    /* split Adler-32 into component sums */
    sum2 = (adler >> 16) & 0xffff;
    adler &= 0xffff;

    /* in case user likes doing a byte at a time, keep it fast */
    if (len == 1) {
        adler += buf[0];
        if (adler >= BASE)
            adler -= BASE;
        sum2 += adler;
        if (sum2 >= BASE)
            sum2 -= BASE;
        return adler | (sum2 << 16);
    }

    /* initial Adler-32 value (deferred check for len == 1 speed) */
    if (buf == Z_NULL)
        return 1L;

    /* in case short lengths are provided, keep it somewhat fast */
    if (len < 16) {
        while (len--) {
            adler += *buf++;
            sum2 += adler;
        }
        if (adler >= BASE)
            adler -= BASE;
        MOD28(sum2);            /* only added so many BASE's */
        return adler | (sum2 << 16);
    }

    /* do length NMAX blocks -- requires just one modulo operation */
    while (len >= NMAX) {
        len -= NMAX;
        n = NMAX / 16;          /* NMAX is divisible by 16 */
        do {
            DO16(buf);          /* 16 sums unrolled */
            buf += 16;
        } while (--n);
        MOD(adler);
        MOD(sum2);
    }

    /* do remaining bytes (less than NMAX, still just one modulo) */
    if (len) {                  /* avoid modulos if none remaining */
        while (len >= 16) {
            len -= 16;
            DO16(buf);
            buf += 16;
        }
        while (len--) {
            adler += *buf++;
            sum2 += adler;
        }
        MOD(adler);
        MOD(sum2);
    }

    /* return recombined sums */
    return adler | (sum2 << 16);
}

typedef enum { SAFE_IOP_TYPE_S32 = 1,
               SAFE_IOP_TYPE_U32,
               SAFE_IOP_TYPE_DEFAULT = SAFE_IOP_TYPE_S32,
               } safe_type_t;

#define SAFE_IOP_TYPE_PREFIXES "us"

#define __sio(x) OPAQUE_SAFE_IOP_PREFIX_ ## x
#define OPAQUE_SAFE_IOP_PREFIX_var(x) __sio(VARIABLE_ ## x)
#define OPAQUE_SAFE_IOP_PREFIX_m(x) __sio(MACRO_ ## x)

#define OPAQUE_SAFE_IOP_PREFIX_MACRO_smax(_a) \
  ((typeof(_a))(~((typeof(_a)) 1 << ((sizeof(typeof(_a)) * CHAR_BIT) - 1))))
#define OPAQUE_SAFE_IOP_PREFIX_MACRO_smin(_a) \
  ((typeof(_a))(-__sio(m)(smax)(_a) - 1))
#define OPAQUE_SAFE_IOP_PREFIX_MACRO_umax(_a) ((typeof(_a))(~((typeof(_a)) 0)))

#define OPAQUE_SAFE_IOP_PREFIX_MACRO_type_enforce(__A, __B) \
  ((((__sio(m)(smin)(__A) <= ((typeof(__A))0)) && \
     (__sio(m)(smin)(__B) <= ((typeof(__B))0))) || \
   (((__sio(m)(smin)(__A) > ((typeof(__A))0))) && \
     (__sio(m)(smin)(__B) > ((typeof(__B))0)))) && \
   (sizeof(typeof(__A)) == sizeof(typeof(__B)))) 

#if defined(NDEBUG)
#  define OPAQUE_SAFE_IOP_PREFIX_MACRO_assert(x) (x)
#else
#  define OPAQUE_SAFE_IOP_PREFIX_MACRO_assert(x) ({ assert(x); 1; })
#endif

#define safe_add(_ptr, __a, __b) \
 ({ int __sio(var)(ok) = 0; \
    typeof(__a) __sio(var)(_a) = (__a); \
    typeof(__b) __sio(var)(_b) = (__b); \
    typeof(_ptr) __sio(var)(p) = (_ptr); \
    if (__sio(m)(assert)(__sio(m)(type_enforce)(__sio(var)(_a), \
                                                __sio(var)(_b)))) { \
      if (__sio(m)(smin)(__sio(var)(_a)) <= ((typeof(__sio(var)(_a)))0)) { \
        __sio(var)(ok) = safe_sadd(__sio(var)(p), \
                                   __sio(var)(_a), \
                                   __sio(var)(_b)); \
      } else { \
        __sio(var)(ok) = safe_uadd(__sio(var)(p), \
                                   __sio(var)(_a), \
                                   __sio(var)(_b)); \
      } \
    } \
    __sio(var)(ok); })

#define safe_uadd(_ptr, _a, _b) \
	({ int __sio(var)(ok) = 0; \
	   if ((typeof(_a))(_b) <= (typeof(_a))(__sio(m)(umax)(_a) - (_a))) { \
		 if ((_ptr)) { *((typeof(_a)*)(_ptr)) = (_a) + (_b); } \
		 __sio(var)(ok) = 1; \
	   } __sio(var)(ok); })


#define safe_sadd(_ptr, _a, _b) \
	({ int __sio(var)(ok) = 1; \
	   if (((_b) > (typeof(_a))0) && ((_a) > (typeof(_a))0)) { /*>0*/ \
		 if ((_a) > (typeof(_a))(__sio(m)(smax)(_a) - (_b))) __sio(var)(ok) = 0; \
	   } else if (!((_b) > (typeof(_a))0) && !((_a) > (typeof(_a))0)) { /*<0*/ \
		 if ((_a) < (typeof(_a))(__sio(m)(smin)(_a) - (_b))) __sio(var)(ok) = 0; \
	   } \
	   if (__sio(var)(ok) && (_ptr)) { *((typeof(_a)*)(_ptr)) = (_a) + (_b); } \
	   __sio(var)(ok); })

#define safe_mul(_ptr, __a, __b) \
	({ int __sio(var)(ok) = 0; \
	   typeof(__a) __sio(var)(_a) = (__a); \
	   typeof(__b) __sio(var)(_b) = (__b); \
	   typeof(_ptr) __sio(var)(p) = (_ptr); \
	   if (__sio(m)(assert)(__sio(m)(type_enforce)(__sio(var)(_a), \
												   __sio(var)(_b)))) { \
		 if (__sio(m)(umax)(__sio(var)(_a)) <= ((typeof(__sio(var)(_a)))0)) { \
		   __sio(var)(ok) = safe_smul(__sio(var)(p), \
									  __sio(var)(_a), \
									  __sio(var)(_b)); \
		 } else { \
		   __sio(var)(ok) = safe_umul(__sio(var)(p), \
									  __sio(var)(_a), \
									  __sio(var)(_b)); \
		 } \
	   } \
	   __sio(var)(ok); })


#define safe_umul(_ptr, _a, _b) \
	({ int __sio(var)(ok) = 0; \
	   if (!(_b) || (_a) <= (__sio(m)(umax)(_a) / (_b))) { \
		 __sio(var)(ok) = 1; \
		 if ((_ptr)) { *((typeof(_a)*)(_ptr)) = (_a) * (_b); } \
	   } \
	   __sio(var)(ok); }) 



#define safe_smul(_ptr, _a, _b) \
	({ int __sio(var)(ok) = 1; \
	  if ((_a) > 0) {  /* a is positive */ \
		if ((_b) > 0) {  /* b and a are positive */ \
		  if ((_a) > (__sio(m)(smax)(_a) / (_b))) { \
			__sio(var)(ok) = 0; \
		  } \
		} /* end if a and b are positive */ \
		else { /* a positive, b non-positive */ \
		  if ((_b) < (__sio(m)(smin)(_a) / (_a))) { \
			__sio(var)(ok) = 0; \
		  } \
		} /* a positive, b non-positive */ \
	  } /* end if a is positive */ \
	  else { /* a is non-positive */ \
		if ((_b) > 0) { /* a is non-positive, b is positive */ \
		  if ((_a) < (__sio(m)(smin)(_a) / (_b))) { \
		  __sio(var)(ok) = 0; \
		  } \
		} /* end if a is non-positive, b is positive */ \
		else { /* a and b are non-positive */ \
		  if( ((_a) != 0) && ((_b) < (__sio(m)(smax)(_a) / (_a)))) { \
			__sio(var)(ok) = 0; \
		  } \
		} /* end if a and b are non-positive */ \
	  } /* end if a is non-positive */ \
	  if (__sio(var)(ok) && (_ptr)) { *((typeof(_a)*)(_ptr)) = (_a) * (_b); } \
	  __sio(var)(ok); }) 

struct Options{
	const char* inputfile;
	const char* outputfile;
};

struct Options gOptions;

struct node{
	char classname[BUF];
	node* nextnode;
};

int modifyNum;

typedef uint8_t u1;
typedef uint16_t u2;
typedef uint32_t u4;
typedef uint64_t u8;
typedef int8_t s1;
typedef int16_t s2;
typedef int32_t s4;
typedef int64_t s8;

typedef u1 OpcodeFlags;
typedef u1 InstructionWidth;

#define kPackedSwitchSignature  0x0100
#define kSparseSwitchSignature  0x0200
#define kArrayDataSignature     0x0300

#define kNumPackedOpcodes 0x100
#define __BYTE_ORDER __LITTLE_ENDIAN

#if __BYTE_ORDER == __LITTLE_ENDIAN
# define SWAP2(_value)      (_value)
# define SWAP4(_value)      (_value)
# define SWAP8(_value)      (_value)
#else
# define SWAP2(_value)      endianSwapU2((_value))
# define SWAP4(_value)      endianSwapU4((_value))
# define SWAP8(_value)      endianSwapU8((_value))

static u2 endianSwapU2(u2 value) {
    return (value >> 8) | (value << 8);
}
static u4 endianSwapU4(u4 value) {
    /* ABCD --> CDAB --> DCBA */
    value = (value >> 16) | (value << 16);
    return ((value & 0xff00ff00) >> 8) | ((value << 8) & 0xff00ff00);
}
static u8 endianSwapU8(u8 value) {
    /* ABCDEFGH --> EFGHABCD --> GHEFCDAB --> HGFEDCBA */
    value = (value >> 32) | (value << 32);
    value = ((value & 0xffff0000ffff0000ULL) >> 16) |
            ((value << 16) & 0xffff0000ffff0000ULL);
    return ((value & 0xff00ff00ff00ff00ULL) >> 8) |
           ((value << 8) & 0xff00ff00ff00ff00ULL);
}
#endif

#define SWAP_FIELD2(_field) (_field) = SWAP2(_field)
#define SWAP_FIELD4(_field) (_field) = SWAP4(_field)
#define SWAP_FIELD8(_field) (_field) = SWAP8(_field)

struct node* classlist = NULL;
struct node* current = NULL;

enum {
	kDexEndianConstant = 0x12345678, /* the endianness indicator */
	kDexNoIndex = 0xffffffff, /* not a valid index value */
};

enum { kSHA1DigestLen = 20,
       kSHA1DigestOutputLen = kSHA1DigestLen*2 +1 };

enum {
	ACC_PUBLIC = 0x00000001,       // class, field, method, ic
	ACC_PRIVATE = 0x00000002,       // field, method, ic
	ACC_PROTECTED = 0x00000004,       // field, method, ic
	ACC_STATIC = 0x00000008,       // field, method, ic
	ACC_FINAL = 0x00000010,       // class, field, method, ic
	ACC_SYNCHRONIZED = 0x00000020,       // method (only allowed on natives)
	ACC_SUPER = 0x00000020,       // class (not used in Dalvik)
	ACC_VOLATILE = 0x00000040,       // field
	ACC_BRIDGE = 0x00000040,       // method (1.5)
	ACC_TRANSIENT = 0x00000080,       // field
	ACC_VARARGS = 0x00000080,       // method (1.5)
	ACC_NATIVE = 0x00000100,       // method
	ACC_INTERFACE = 0x00000200,       // class, ic
	ACC_ABSTRACT = 0x00000400,       // class, method, ic
	ACC_STRICT = 0x00000800,       // method
	ACC_SYNTHETIC = 0x00001000,       // field, method, ic
	ACC_ANNOTATION = 0x00002000,       // class, ic (1.5)
	ACC_ENUM = 0x00004000,       // class, field, ic (1.5)
	ACC_CONSTRUCTOR = 0x00010000,       // method (Dalvik only)
	ACC_DECLARED_SYNCHRONIZED = 0x00020000,       // method (Dalvik only)
	ACC_CLASS_MASK = (ACC_PUBLIC | ACC_FINAL | ACC_INTERFACE | ACC_ABSTRACT
			| ACC_SYNTHETIC | ACC_ANNOTATION | ACC_ENUM),
	ACC_INNER_CLASS_MASK = (ACC_CLASS_MASK | ACC_PRIVATE | ACC_PROTECTED
			| ACC_STATIC),
	ACC_FIELD_MASK = (ACC_PUBLIC | ACC_PRIVATE | ACC_PROTECTED | ACC_STATIC
			| ACC_FINAL | ACC_VOLATILE | ACC_TRANSIENT | ACC_SYNTHETIC
			| ACC_ENUM),
	ACC_METHOD_MASK = (ACC_PUBLIC | ACC_PRIVATE | ACC_PROTECTED | ACC_STATIC
			| ACC_FINAL | ACC_SYNCHRONIZED | ACC_BRIDGE | ACC_VARARGS
			| ACC_NATIVE | ACC_ABSTRACT | ACC_STRICT | ACC_SYNTHETIC
			| ACC_CONSTRUCTOR | ACC_DECLARED_SYNCHRONIZED),
};

enum {
	kDexVisibilityBuild = 0x00, /* annotation visibility */
	kDexVisibilityRuntime = 0x01,
	kDexVisibilitySystem = 0x02,

	kDexAnnotationByte = 0x00,
	kDexAnnotationShort = 0x02,
	kDexAnnotationChar = 0x03,
	kDexAnnotationInt = 0x04,
	kDexAnnotationLong = 0x06,
	kDexAnnotationFloat = 0x10,
	kDexAnnotationDouble = 0x11,
	kDexAnnotationString = 0x17,
	kDexAnnotationType = 0x18,
	kDexAnnotationField = 0x19,
	kDexAnnotationMethod = 0x1a,
	kDexAnnotationEnum = 0x1b,
	kDexAnnotationArray = 0x1c,
	kDexAnnotationAnnotation = 0x1d,
	kDexAnnotationNull = 0x1e,
	kDexAnnotationBoolean = 0x1f,

	kDexAnnotationValueTypeMask = 0x1f, /* low 5 bits */
	kDexAnnotationValueArgShift = 5,
};

/* encode the result of unzipping to a file */
enum UnzipToFileResult {
	kUTFRSuccess = 0,
	kUTFRGenericFailure,
	kUTFRBadArgs,
	kUTFRNotZip,
	kUTFRNoClassesDex,
	kUTFROutputFileProblem,
	kUTFRBadZip,
};

enum {
	kDexTypeHeaderItem = 0x0000,
	kDexTypeStringIdItem = 0x0001,
	kDexTypeTypeIdItem = 0x0002,
	kDexTypeProtoIdItem = 0x0003,
	kDexTypeFieldIdItem = 0x0004,
	kDexTypeMethodIdItem = 0x0005,
	kDexTypeClassDefItem = 0x0006,
	kDexTypeMapList = 0x1000,
	kDexTypeTypeList = 0x1001,
	kDexTypeAnnotationSetRefList = 0x1002,
	kDexTypeAnnotationSetItem = 0x1003,
	kDexTypeClassDataItem = 0x2000,
	kDexTypeCodeItem = 0x2001,
	kDexTypeStringDataItem = 0x2002,
	kDexTypeDebugInfoItem = 0x2003,
	kDexTypeAnnotationItem = 0x2004,
	kDexTypeEncodedArrayItem = 0x2005,
	kDexTypeAnnotationsDirectoryItem = 0x2006,
};

enum {
	DBG_END_SEQUENCE = 0x00,
	DBG_ADVANCE_PC = 0x01,
	DBG_ADVANCE_LINE = 0x02,
	DBG_START_LOCAL = 0x03,
	DBG_START_LOCAL_EXTENDED = 0x04,
	DBG_END_LOCAL = 0x05,
	DBG_RESTART_LOCAL = 0x06,
	DBG_SET_PROLOGUE_END = 0x07,
	DBG_SET_EPILOGUE_BEGIN = 0x08,
	DBG_SET_FILE = 0x09,
	DBG_FIRST_SPECIAL = 0x0a,
	DBG_LINE_BASE = -4,
	DBG_LINE_RANGE = 15,
};

struct DexAnnotationItem {
    u1  visibility;
    u1  annotation[1];              /* data in encoded_annotation format */
};

enum {
    kDexChunkClassLookup            = 0x434c4b50,   /* CLKP */
    kDexChunkRegisterMaps           = 0x524d4150,   /* RMAP */
    kDexChunkEnd                    = 0x41454e44,   /* AEND */
};

enum {
    kDexParseDefault            = 0,
    kDexParseVerifyChecksum     = 1,
    kDexParseContinueOnError    = (1 << 1),
};

enum AccessFor {
    kAccessForClass = 0, kAccessForMethod = 1, kAccessForField = 2,
    kAccessForMAX
};

enum InstructionIndexType {
    kIndexUnknown = 0,
    kIndexNone,         // has no index
    kIndexVaries,       // "It depends." Used for throw-verification-error
    kIndexTypeRef,      // type reference index
    kIndexStringRef,    // string reference index
    kIndexMethodRef,    // method reference index
    kIndexFieldRef,     // field reference index
    kIndexInlineMethod, // inline method index (for inline linked methods)
    kIndexVtableOffset, // vtable offset (for static linked methods)
    kIndexFieldOffset   // field offset (for static linked fields)
};

enum Opcode {
    // BEGIN(libdex-opcode-enum); GENERATED AUTOMATICALLY BY opcode-gen
    OP_NOP                          = 0x00,
    OP_MOVE                         = 0x01,
    OP_MOVE_FROM16                  = 0x02,
    OP_MOVE_16                      = 0x03,
    OP_MOVE_WIDE                    = 0x04,
    OP_MOVE_WIDE_FROM16             = 0x05,
    OP_MOVE_WIDE_16                 = 0x06,
    OP_MOVE_OBJECT                  = 0x07,
    OP_MOVE_OBJECT_FROM16           = 0x08,
    OP_MOVE_OBJECT_16               = 0x09,
    OP_MOVE_RESULT                  = 0x0a,
    OP_MOVE_RESULT_WIDE             = 0x0b,
    OP_MOVE_RESULT_OBJECT           = 0x0c,
    OP_MOVE_EXCEPTION               = 0x0d,
    OP_RETURN_VOID                  = 0x0e,
    OP_RETURN                       = 0x0f,
    OP_RETURN_WIDE                  = 0x10,
    OP_RETURN_OBJECT                = 0x11,
    OP_CONST_4                      = 0x12,
    OP_CONST_16                     = 0x13,
    OP_CONST                        = 0x14,
    OP_CONST_HIGH16                 = 0x15,
    OP_CONST_WIDE_16                = 0x16,
    OP_CONST_WIDE_32                = 0x17,
    OP_CONST_WIDE                   = 0x18,
    OP_CONST_WIDE_HIGH16            = 0x19,
    OP_CONST_STRING                 = 0x1a,
    OP_CONST_STRING_JUMBO           = 0x1b,
    OP_CONST_CLASS                  = 0x1c,
    OP_MONITOR_ENTER                = 0x1d,
    OP_MONITOR_EXIT                 = 0x1e,
    OP_CHECK_CAST                   = 0x1f,
    OP_INSTANCE_OF                  = 0x20,
    OP_ARRAY_LENGTH                 = 0x21,
    OP_NEW_INSTANCE                 = 0x22,
    OP_NEW_ARRAY                    = 0x23,
    OP_FILLED_NEW_ARRAY             = 0x24,
    OP_FILLED_NEW_ARRAY_RANGE       = 0x25,
    OP_FILL_ARRAY_DATA              = 0x26,
    OP_THROW                        = 0x27,
    OP_GOTO                         = 0x28,
    OP_GOTO_16                      = 0x29,
    OP_GOTO_32                      = 0x2a,
    OP_PACKED_SWITCH                = 0x2b,
    OP_SPARSE_SWITCH                = 0x2c,
    OP_CMPL_FLOAT                   = 0x2d,
    OP_CMPG_FLOAT                   = 0x2e,
    OP_CMPL_DOUBLE                  = 0x2f,
    OP_CMPG_DOUBLE                  = 0x30,
    OP_CMP_LONG                     = 0x31,
    OP_IF_EQ                        = 0x32,
    OP_IF_NE                        = 0x33,
    OP_IF_LT                        = 0x34,
    OP_IF_GE                        = 0x35,
    OP_IF_GT                        = 0x36,
    OP_IF_LE                        = 0x37,
    OP_IF_EQZ                       = 0x38,
    OP_IF_NEZ                       = 0x39,
    OP_IF_LTZ                       = 0x3a,
    OP_IF_GEZ                       = 0x3b,
    OP_IF_GTZ                       = 0x3c,
    OP_IF_LEZ                       = 0x3d,
    OP_UNUSED_3E                    = 0x3e,
    OP_UNUSED_3F                    = 0x3f,
    OP_UNUSED_40                    = 0x40,
    OP_UNUSED_41                    = 0x41,
    OP_UNUSED_42                    = 0x42,
    OP_UNUSED_43                    = 0x43,
    OP_AGET                         = 0x44,
    OP_AGET_WIDE                    = 0x45,
    OP_AGET_OBJECT                  = 0x46,
    OP_AGET_BOOLEAN                 = 0x47,
    OP_AGET_BYTE                    = 0x48,
    OP_AGET_CHAR                    = 0x49,
    OP_AGET_SHORT                   = 0x4a,
    OP_APUT                         = 0x4b,
    OP_APUT_WIDE                    = 0x4c,
    OP_APUT_OBJECT                  = 0x4d,
    OP_APUT_BOOLEAN                 = 0x4e,
    OP_APUT_BYTE                    = 0x4f,
    OP_APUT_CHAR                    = 0x50,
    OP_APUT_SHORT                   = 0x51,
    OP_IGET                         = 0x52,
    OP_IGET_WIDE                    = 0x53,
    OP_IGET_OBJECT                  = 0x54,
    OP_IGET_BOOLEAN                 = 0x55,
    OP_IGET_BYTE                    = 0x56,
    OP_IGET_CHAR                    = 0x57,
    OP_IGET_SHORT                   = 0x58,
    OP_IPUT                         = 0x59,
    OP_IPUT_WIDE                    = 0x5a,
    OP_IPUT_OBJECT                  = 0x5b,
    OP_IPUT_BOOLEAN                 = 0x5c,
    OP_IPUT_BYTE                    = 0x5d,
    OP_IPUT_CHAR                    = 0x5e,
    OP_IPUT_SHORT                   = 0x5f,
    OP_SGET                         = 0x60,
    OP_SGET_WIDE                    = 0x61,
    OP_SGET_OBJECT                  = 0x62,
    OP_SGET_BOOLEAN                 = 0x63,
    OP_SGET_BYTE                    = 0x64,
    OP_SGET_CHAR                    = 0x65,
    OP_SGET_SHORT                   = 0x66,
    OP_SPUT                         = 0x67,
    OP_SPUT_WIDE                    = 0x68,
    OP_SPUT_OBJECT                  = 0x69,
    OP_SPUT_BOOLEAN                 = 0x6a,
    OP_SPUT_BYTE                    = 0x6b,
    OP_SPUT_CHAR                    = 0x6c,
    OP_SPUT_SHORT                   = 0x6d,
    OP_INVOKE_VIRTUAL               = 0x6e,
    OP_INVOKE_SUPER                 = 0x6f,
    OP_INVOKE_DIRECT                = 0x70,
    OP_INVOKE_STATIC                = 0x71,
    OP_INVOKE_INTERFACE             = 0x72,
    OP_UNUSED_73                    = 0x73,
    OP_INVOKE_VIRTUAL_RANGE         = 0x74,
    OP_INVOKE_SUPER_RANGE           = 0x75,
    OP_INVOKE_DIRECT_RANGE          = 0x76,
    OP_INVOKE_STATIC_RANGE          = 0x77,
    OP_INVOKE_INTERFACE_RANGE       = 0x78,
    OP_UNUSED_79                    = 0x79,
    OP_UNUSED_7A                    = 0x7a,
    OP_NEG_INT                      = 0x7b,
    OP_NOT_INT                      = 0x7c,
    OP_NEG_LONG                     = 0x7d,
    OP_NOT_LONG                     = 0x7e,
    OP_NEG_FLOAT                    = 0x7f,
    OP_NEG_DOUBLE                   = 0x80,
    OP_INT_TO_LONG                  = 0x81,
    OP_INT_TO_FLOAT                 = 0x82,
    OP_INT_TO_DOUBLE                = 0x83,
    OP_LONG_TO_INT                  = 0x84,
    OP_LONG_TO_FLOAT                = 0x85,
    OP_LONG_TO_DOUBLE               = 0x86,
    OP_FLOAT_TO_INT                 = 0x87,
    OP_FLOAT_TO_LONG                = 0x88,
    OP_FLOAT_TO_DOUBLE              = 0x89,
    OP_DOUBLE_TO_INT                = 0x8a,
    OP_DOUBLE_TO_LONG               = 0x8b,
    OP_DOUBLE_TO_FLOAT              = 0x8c,
    OP_INT_TO_BYTE                  = 0x8d,
    OP_INT_TO_CHAR                  = 0x8e,
    OP_INT_TO_SHORT                 = 0x8f,
    OP_ADD_INT                      = 0x90,
    OP_SUB_INT                      = 0x91,
    OP_MUL_INT                      = 0x92,
    OP_DIV_INT                      = 0x93,
    OP_REM_INT                      = 0x94,
    OP_AND_INT                      = 0x95,
    OP_OR_INT                       = 0x96,
    OP_XOR_INT                      = 0x97,
    OP_SHL_INT                      = 0x98,
    OP_SHR_INT                      = 0x99,
    OP_USHR_INT                     = 0x9a,
    OP_ADD_LONG                     = 0x9b,
    OP_SUB_LONG                     = 0x9c,
    OP_MUL_LONG                     = 0x9d,
    OP_DIV_LONG                     = 0x9e,
    OP_REM_LONG                     = 0x9f,
    OP_AND_LONG                     = 0xa0,
    OP_OR_LONG                      = 0xa1,
    OP_XOR_LONG                     = 0xa2,
    OP_SHL_LONG                     = 0xa3,
    OP_SHR_LONG                     = 0xa4,
    OP_USHR_LONG                    = 0xa5,
    OP_ADD_FLOAT                    = 0xa6,
    OP_SUB_FLOAT                    = 0xa7,
	OP_MUL_FLOAT					= 0xa8,
	OP_DIV_FLOAT					= 0xa9,
	OP_REM_FLOAT					= 0xaa,
	OP_ADD_DOUBLE					= 0xab,
	OP_SUB_DOUBLE					= 0xac,
	OP_MUL_DOUBLE					= 0xad,
	OP_DIV_DOUBLE					= 0xae,
	OP_REM_DOUBLE					= 0xaf,
	OP_ADD_INT_2ADDR				= 0xb0,
	OP_SUB_INT_2ADDR				= 0xb1,
	OP_MUL_INT_2ADDR				= 0xb2,
	OP_DIV_INT_2ADDR				= 0xb3,
	OP_REM_INT_2ADDR				= 0xb4,
	OP_AND_INT_2ADDR				= 0xb5,
	OP_OR_INT_2ADDR 				= 0xb6,
	OP_XOR_INT_2ADDR				= 0xb7,
	OP_SHL_INT_2ADDR				= 0xb8,
	OP_SHR_INT_2ADDR				= 0xb9,
	OP_USHR_INT_2ADDR				= 0xba,
	OP_ADD_LONG_2ADDR				= 0xbb,
	OP_SUB_LONG_2ADDR				= 0xbc,
	OP_MUL_LONG_2ADDR				= 0xbd,
	OP_DIV_LONG_2ADDR				= 0xbe,
	OP_REM_LONG_2ADDR				= 0xbf,
	OP_AND_LONG_2ADDR				= 0xc0,
	OP_OR_LONG_2ADDR				= 0xc1,
	OP_XOR_LONG_2ADDR				= 0xc2,
	OP_SHL_LONG_2ADDR				= 0xc3,
	OP_SHR_LONG_2ADDR				= 0xc4,
	OP_USHR_LONG_2ADDR				= 0xc5,
	OP_ADD_FLOAT_2ADDR				= 0xc6,
	OP_SUB_FLOAT_2ADDR				= 0xc7,
	OP_MUL_FLOAT_2ADDR				= 0xc8,
	OP_DIV_FLOAT_2ADDR				= 0xc9,
	OP_REM_FLOAT_2ADDR				= 0xca,
	OP_ADD_DOUBLE_2ADDR 			= 0xcb,
	OP_SUB_DOUBLE_2ADDR 			= 0xcc,
	OP_MUL_DOUBLE_2ADDR 			= 0xcd,
	OP_DIV_DOUBLE_2ADDR 			= 0xce,
	OP_REM_DOUBLE_2ADDR 			= 0xcf,
	OP_ADD_INT_LIT16				= 0xd0,
	OP_RSUB_INT 					= 0xd1,
	OP_MUL_INT_LIT16				= 0xd2,
	OP_DIV_INT_LIT16				= 0xd3,
	OP_REM_INT_LIT16				= 0xd4,
	OP_AND_INT_LIT16				= 0xd5,
	OP_OR_INT_LIT16 				= 0xd6,
	OP_XOR_INT_LIT16				= 0xd7,
	OP_ADD_INT_LIT8 				= 0xd8,
	OP_RSUB_INT_LIT8				= 0xd9,
	OP_MUL_INT_LIT8 				= 0xda,
	OP_DIV_INT_LIT8 				= 0xdb,
	OP_REM_INT_LIT8 				= 0xdc,
	OP_AND_INT_LIT8 				= 0xdd,
	OP_OR_INT_LIT8					= 0xde,
	OP_XOR_INT_LIT8 				= 0xdf,
	OP_SHL_INT_LIT8 				= 0xe0,
	OP_SHR_INT_LIT8 				= 0xe1,
	OP_USHR_INT_LIT8				= 0xe2,
	OP_IGET_VOLATILE				= 0xe3,
	OP_IPUT_VOLATILE				= 0xe4,
	OP_SGET_VOLATILE				= 0xe5,
	OP_SPUT_VOLATILE				= 0xe6,
	OP_IGET_OBJECT_VOLATILE 		= 0xe7,
	OP_IGET_WIDE_VOLATILE			= 0xe8,
	OP_IPUT_WIDE_VOLATILE			= 0xe9,
	OP_SGET_WIDE_VOLATILE			= 0xea,
	OP_SPUT_WIDE_VOLATILE			= 0xeb,
	OP_BREAKPOINT					= 0xec,
	OP_THROW_VERIFICATION_ERROR 	= 0xed,
	OP_EXECUTE_INLINE				= 0xee,
	OP_EXECUTE_INLINE_RANGE 		= 0xef,
	OP_INVOKE_OBJECT_INIT_RANGE 	= 0xf0,
	OP_RETURN_VOID_BARRIER			= 0xf1,
	OP_IGET_QUICK					= 0xf2,
	OP_IGET_WIDE_QUICK				= 0xf3,
	OP_IGET_OBJECT_QUICK			= 0xf4,
	OP_IPUT_QUICK					= 0xf5,
	OP_IPUT_WIDE_QUICK				= 0xf6,
	OP_IPUT_OBJECT_QUICK			= 0xf7,
	OP_INVOKE_VIRTUAL_QUICK 		= 0xf8,
	OP_INVOKE_VIRTUAL_QUICK_RANGE	= 0xf9,
	OP_INVOKE_SUPER_QUICK			= 0xfa,
	OP_INVOKE_SUPER_QUICK_RANGE 	= 0xfb,
	OP_IPUT_OBJECT_VOLATILE 		= 0xfc,
	OP_SGET_OBJECT_VOLATILE 		= 0xfd,
	OP_SPUT_OBJECT_VOLATILE 		= 0xfe,
	OP_UNUSED_FF					= 0xff,
	// END(libdex-opcode-enum)
};

enum InstructionFormat {
    kFmt00x = 0,    // unknown format (also used for "breakpoint" opcode)
    kFmt10x,        // op
    kFmt12x,        // op vA, vB
    kFmt11n,        // op vA, #+B
    kFmt11x,        // op vAA
    kFmt10t,        // op +AA
    kFmt20bc,       // [opt] op AA, thing@BBBB
    kFmt20t,        // op +AAAA
    kFmt22x,        // op vAA, vBBBB
    kFmt21t,        // op vAA, +BBBB
    kFmt21s,        // op vAA, #+BBBB
    kFmt21h,        // op vAA, #+BBBB00000[00000000]
    kFmt21c,        // op vAA, thing@BBBB
    kFmt23x,        // op vAA, vBB, vCC
    kFmt22b,        // op vAA, vBB, #+CC
    kFmt22t,        // op vA, vB, +CCCC
    kFmt22s,        // op vA, vB, #+CCCC
    kFmt22c,        // op vA, vB, thing@CCCC
    kFmt22cs,       // [opt] op vA, vB, field offset CCCC
    kFmt30t,        // op +AAAAAAAA
    kFmt32x,        // op vAAAA, vBBBB
    kFmt31i,        // op vAA, #+BBBBBBBB
    kFmt31t,        // op vAA, +BBBBBBBB
    kFmt31c,        // op vAA, string@BBBBBBBB
    kFmt35c,        // op {vC,vD,vE,vF,vG}, thing@BBBB
    kFmt35ms,       // [opt] invoke-virtual+super
    kFmt3rc,        // op {vCCCC .. v(CCCC+AA-1)}, thing@BBBB
    kFmt3rms,       // [opt] invoke-virtual+super/range
    kFmt51l,        // op vAA, #+BBBBBBBBBBBBBBBB
    kFmt35mi,       // [opt] inline invoke
    kFmt3rmi,       // [opt] inline invoke/range
};

enum OpcodeFlagsBits {
    kInstrCanBranch     = 1,        // conditional or unconditional branch
    kInstrCanContinue   = 1 << 1,   // flow can continue to next statement
    kInstrCanSwitch     = 1 << 2,   // switch statement
    kInstrCanThrow      = 1 << 3,   // could cause an exception to be thrown
    kInstrCanReturn     = 1 << 4,   // returns, no additional statements
    kInstrInvoke        = 1 << 5,   // a flavor of invoke
};

struct SHA1_CTX {
    unsigned long state[5];
    unsigned long count[2];
    unsigned char buffer[64];
};

struct DexOptHeader {
	u1 magic[8]; /* includes version number */
	u4 dexOffset; /* file offset of DEX header */
	u4 dexLength;
	u4 depsOffset; /* offset of optimized DEX dependency table */
	u4 depsLength;
	u4 optOffset; /* file offset of optimized data tables */
	u4 optLength;
	u4 flags; /* some info flags */
	u4 checksum; /* adler32 checksum covering deps/opt */
	/* pad for 64-bit alignment if necessary */
};

struct DexHeader {
	u1 magic[8]; /* includes version number */
	u4 checksum; /* adler32 checksum */
	u1 signature[kSHA1DigestLen]; /* SHA-1 hash */
	u4 fileSize; /* length of entire file */
	u4 headerSize; /* offset to start of next section */
	u4 endianTag;
	u4 linkSize;
	u4 linkOff;
	u4 mapOff;
	u4 stringIdsSize;
	u4 stringIdsOff;
	u4 typeIdsSize;
	u4 typeIdsOff;
	u4 protoIdsSize;
	u4 protoIdsOff;
	u4 fieldIdsSize;
	u4 fieldIdsOff;
	u4 methodIdsSize;
	u4 methodIdsOff;
	u4 classDefsSize;
	u4 classDefsOff;
	u4 dataSize;
	u4 dataOff;
};

struct DexMapItem {
	u2 type; /* type code (see kDexType* above) */
	u2 unused;
	u4 size; /* count of items of the indicated type */
	u4 offset; /* file offset to the start of data */
};

struct DexMapList {
	u4 size; /* #of entries in list */
	DexMapItem list[1]; /* entries */
};

struct DexStringId {
	u4 stringDataOff; /* file offset to string_data_item */
};

struct DexTypeId {
	u4 descriptorIdx; /* index into stringIds list for type descriptor */
};

struct DexFieldId {
	u2 classIdx; /* index into typeIds list for defining class */
	u2 typeIdx; /* index into typeIds for field type */
	u4 nameIdx; /* index into stringIds for field name */
};

struct DexMethodId {
	u2 classIdx; /* index into typeIds list for defining class */
	u2 protoIdx; /* index into protoIds for method prototype */
	u4 nameIdx; /* index into stringIds for method name */
};

struct DexProtoId {
	u4 shortyIdx; /* index into stringIds for shorty descriptor */
	u4 returnTypeIdx; /* index into typeIds list for return type */
	u4 parametersOff; /* file offset to type_list for parameter types */
};

struct DexClassDef {
	u4 classIdx; /* index into typeIds for this class */
	u4 accessFlags;
	u4 superclassIdx; /* index into typeIds for superclass */
	u4 interfacesOff; /* file offset to DexTypeList */
	u4 sourceFileIdx; /* index into stringIds for source file name */
	u4 annotationsOff; /* file offset to annotations_directory_item */
	u4 classDataOff; /* file offset to class_data_item */
	u4 staticValuesOff; /* file offset to DexEncodedArray */
};

struct DexTypeItem {
	u2 typeIdx; /* index into typeIds */
};

struct DexTypeList {
	u4 size; /* #of entries in list */
	DexTypeItem list[1]; /* entries */
};

struct DexCode {
	u2 registersSize;
	u2 insSize;
	u2 outsSize;
	u2 triesSize;
	u4 debugInfoOff; /* file offset to debug info stream */
	u4 insnsSize; /* size of the insns array, in u2 units */
	u2 insns[1];
	/* followed by optional u2 padding */
	/* followed by try_item[triesSize] */
	/* followed by uleb128 handlersSize */
	/* followed by catch_handler_item[handlersSize] */
};

struct DexLink {
	u1 bleargh;
};

struct DexAnnotationsDirectoryItem {
    u4  classAnnotationsOff;  /* offset to DexAnnotationSetItem */
    u4  fieldsSize;           /* count of DexFieldAnnotationsItem */
    u4  methodsSize;          /* count of DexMethodAnnotationsItem */
    u4  parametersSize;       /* count of DexParameterAnnotationsItem */
    /* followed by DexFieldAnnotationsItem[fieldsSize] */
    /* followed by DexMethodAnnotationsItem[methodsSize] */
    /* followed by DexParameterAnnotationsItem[parametersSize] */
};

struct DexFieldAnnotationsItem {
    u4  fieldIdx;
    u4  annotationsOff;             /* offset to DexAnnotationSetItem */
};

struct DexMethodAnnotationsItem {
    u4  methodIdx;
    u4  annotationsOff;             /* offset to DexAnnotationSetItem */
};

struct DexParameterAnnotationsItem {
    u4  methodIdx;
    u4  annotationsOff;             /* offset to DexAnotationSetRefList */
};

struct DexAnnotationSetRefItem {
    u4  annotationsOff;             /* offset to DexAnnotationSetItem */
};

struct DexAnnotationSetRefList {
    u4  size;
    DexAnnotationSetRefItem list[1];
};

struct DexAnnotationSetItem {
    u4  size;
    u4  entries[1];                 /* offset to DexAnnotationItem */
};

struct DexClassLookup {
	int size;                       // total size, including "size"
	int numEntries;                 // size of table[]; always power of 2
	struct {
		u4 classDescriptorHash;    // class descriptor hash code
		int classDescriptorOffset;  // in bytes, from start of DEX
		int classDefOffset;         // in bytes, from start of DEX
	} table[1];
};

struct DexFile {
	/* directly-mapped "opt" header */
	const DexOptHeader* pOptHeader;

	/* pointers to directly-mapped structs and arrays in base DEX */
	const DexHeader* pHeader;
	const DexStringId* pStringIds;
	const DexTypeId* pTypeIds;
	const DexFieldId* pFieldIds;
	const DexMethodId* pMethodIds;
	const DexProtoId* pProtoIds;
	const DexClassDef* pClassDefs;
	const DexLink* pLinkData;

	const DexClassLookup* pClassLookup;
	const void* pRegisterMapPool;       // RegisterMapClassPool

	/* points to start of DEX file data */
	const u1* baseAddr;

	/* track memory overhead for auxillary structures */
	int overhead;

	/* additional app-specific data structures associated with the DEX */
	//void*               auxData;
};

struct MemMapping {
	void* addr; /* start of data */
	size_t length; /* length of data */

	void* baseAddr; /* page-aligned base address */
	size_t baseLength; /* length of mapping */
};

struct DexDataMap {
	u4 count; /* number of items currently in the map */
	u4 max; /* maximum number of items that may be held */
	u4* offsets; /* array of item offsets */
	u2* types; /* corresponding array of item types */
};

struct CheckState {
	const DexHeader* pHeader;
	const u1* fileStart;
	const u1* fileEnd;      // points to fileStart + fileLen
	u4 fileLen;
	DexDataMap* pDataMap;     // set after map verification
	const DexFile* pDexFile;     // set after intraitem verification

	/*
	 * bitmap of type_id indices that have been used to define classes;
	 * initialized immediately before class_def cross-verification, and
	 * freed immediately after it
	 */
	u4* pDefinedClassBits;

	const void* previousItem; // set during section iteration
};

struct DexClassDataHeader {
	u4 staticFieldsSize;
	u4 instanceFieldsSize;
	u4 directMethodsSize;
	u4 virtualMethodsSize;
};

struct DexField {
	u4 fieldIdx; /* index to a field_id_item */
	u4 accessFlags;
};

struct DexMethod {
	u4 methodIdx; /* index to a method_id_item */
	u4 accessFlags;
	u4 codeOff; /* file offset to a code_item */
};

struct DexClassData {
	DexClassDataHeader header;
	DexField* staticFields;
	DexField* instanceFields;
	DexMethod* directMethods;
	DexMethod* virtualMethods;
};

struct DexProto {
	const DexFile* dexFile; /* file the idx refers to */
	u4 protoIdx; /* index into proto_ids table of dexFile */
};

struct DexParameterIterator {
	const DexProto* proto;
	const DexTypeList* parameters;
	int parameterCount;
	int cursor;
};

struct DexStringCache {
    char* value;          /* the latest value */
    size_t allocatedSize; /* size of the allocated buffer, if allocated */
    char buffer[120];     /* buffer used to hold small-enough results */
};

struct FieldMethodInfo {
    const char* classDescriptor;
    const char* name;
    const char* signature;
};

struct DecodedInstruction {
    u4      vA;
    u4      vB;
    u8      vB_wide;        /* for kFmt51l */
    u4      vC;
    u4      arg[5];         /* vC/D/E/F/G in invoke or filled-new-array */
    Opcode  opcode;
    InstructionIndexType indexType;
};

struct InstructionInfoTables {
    u1*                formats;    /* InstructionFormat elements */
    u1*                indexTypes; /* InstructionIndexType elements */
    OpcodeFlags*       flags;
    InstructionWidth*  widths;
};

struct DexTry {
    u4  startAddr;          /* start address, in 16-bit code units */
    u2  insnCount;          /* instruction count, in 16-bit code units */
    u2  handlerOff;         /* offset in encoded handler data to handlers */
};

struct DexCatchHandler {
    u4          typeIdx;    /* type index of the caught exception type */
    u4          address;    /* handler address */
};

struct DexCatchIterator {
    const u1* pEncodedData;
    bool catchesAll;
    u4 countRemaining;
    DexCatchHandler handler;
};

struct LocalInfo {
    const char *name;
    const char *descriptor;
    const char *signature;
    u2 startAddress;
    bool live;
};

static inline u4 fetch_u4_impl(u4 offset, const u2* insns) {
    return insns[offset] | ((u4) insns[offset+1] << 16);
}

#define FETCH(_offset)      (insns[(_offset)])
#define FETCH_u4(_offset)   (fetch_u4_impl((_offset), insns))
#define INST_A(_inst)       (((u2)(_inst) >> 8) & 0x0f)
#define INST_B(_inst)       ((u2)(_inst) >> 12)
#define INST_AA(_inst)      ((_inst) >> 8)

int readUnsignedLeb128(const u1** pStream) {
	const u1* ptr = *pStream;
	int result = *(ptr++);

	if (result > 0x7f) {
		int cur = *(ptr++);
		result = (result & 0x7f) | ((cur & 0x7f) << 7);
		if (cur > 0x7f) {
			cur = *(ptr++);
			result |= (cur & 0x7f) << 14;
			if (cur > 0x7f) {
				cur = *(ptr++);
				result |= (cur & 0x7f) << 21;
				if (cur > 0x7f) {
					/*
					 * Note: We don't check to see if cur is out of
					 * range here, meaning we tolerate garbage in the
					 * high four-order bits.
					 */
					cur = *(ptr++);
					result |= cur << 28;
				}
			}
		}
	}

	*pStream = ptr;
	return result;
}

int readAndVerifyUnsignedLeb128(const u1** pStream, const u1* limit,
		bool* okay) {
	const u1* ptr = *pStream;
	int result = readUnsignedLeb128(pStream);

	if (((limit != NULL) && (*pStream > limit))
			|| (((*pStream - ptr) == 5) && (ptr[4] > 0x0f))) {
		*okay = false;
	}

	return result;
}

int readSignedLeb128(const u1** pStream) {
	const u1* ptr = *pStream;
	int result = *(ptr++);

	if (result <= 0x7f) {
		result = (result << 25) >> 25;
	} else {
		int cur = *(ptr++);
		result = (result & 0x7f) | ((cur & 0x7f) << 7);
		if (cur <= 0x7f) {
			result = (result << 18) >> 18;
		} else {
			cur = *(ptr++);
			result |= (cur & 0x7f) << 14;
			if (cur <= 0x7f) {
				result = (result << 11) >> 11;
			} else {
				cur = *(ptr++);
				result |= (cur & 0x7f) << 21;
				if (cur <= 0x7f) {
					result = (result << 4) >> 4;
				} else {
					/*
					 * Note: We don't check to see if cur is out of
					 * range here, meaning we tolerate garbage in the
					 * high four-order bits.
					 */
					cur = *(ptr++);
					result |= cur << 28;
				}
			}
		}
	}

	*pStream = ptr;
	return result;
}

int readAndVerifySignedLeb128(const u1** pStream, const u1* limit,
        bool* okay) {
    const u1* ptr = *pStream;
    int result = readSignedLeb128(pStream);

    if (((limit != NULL) && (*pStream > limit))
            || (((*pStream - ptr) == 5) && (ptr[4] > 0x0f))) {
        *okay = false;
    }

    return result;
}

u2 dexGetUtf16FromUtf8(const char** pUtf8Ptr) {
	unsigned int one, two, three;

	one = *(*pUtf8Ptr)++;
	if ((one & 0x80) != 0) {
		/* two- or three-byte encoding */
		two = *(*pUtf8Ptr)++;
		if ((one & 0x20) != 0) {
			/* three-byte encoding */
			three = *(*pUtf8Ptr)++;
			return ((one & 0x0f) << 12) | ((two & 0x3f) << 6) | (three & 0x3f);
		} else {
			/* two-byte encoding */
			return ((one & 0x1f) << 6) | (two & 0x3f);
		}
	} else {
		/* one-byte encoding */
		return one;
	}
}

static inline u4 fileOffset(const CheckState* state, const void* ptr) {
    return ((const u1*) ptr) - state->fileStart;
}

static inline void* filePointer(const CheckState* state, u4 offset) {
    return (void*) (state->fileStart + offset);
}

static inline bool checkPtrRange(const CheckState* state,
        const void* start, const void* end, const char* label) {
    const void* fileStart = state->fileStart;
    const void* fileEnd = state->fileEnd;
    if ((start < fileStart) || (start > fileEnd)
            || (end < start) || (end > fileEnd)) {
        fprintf(stderr, "Bad offset range for %s: %#x..%#x", label,
                fileOffset(state, start), fileOffset(state, end));
        return false;
    }
    return true;
}

#define CHECK_OFFSET_RANGE(_start, _end) {                                  \
        const u1* _startPtr = (const u1*) filePointer(state, (_start));     \
        const u1* _endPtr = (const u1*) filePointer(state, (_end));         \
        if (!checkPtrRange(state, _startPtr, _endPtr,                       \
                        #_start ".." #_end)) {                              \
            return 0;                                                       \
        }                                                                   \
    }

#define CHECK_PTR_RANGE(_start, _end) {                                     \
        if (!checkPtrRange(state, (_start), (_end), #_start ".." #_end)) {  \
            return 0;                                                       \
        }                                                                   \
    }

#define CHECK_LIST_SIZE(_ptr, _count, _elemSize) {                          \
        const u1* _start = (const u1*) (_ptr);                              \
        const u1* _end = _start + ((_count) * (_elemSize));                 \
        if (!safe_mul(NULL, (_count), (_elemSize)) ||                       \
            !checkPtrRange(state, _start, _end, #_ptr)) {                   \
            return 0;                                                       \
        }                                                                   \
    }

#define SWAP_OFFSET4(_field) {                                              \
        SWAP_FIELD4((_field));                                              \
    }

#define CHECK_INDEX(_field, _limit) {                                       \
        if ((_field) >= (_limit)) {                                         \
            fprintf(stderr, "Bad index: %s(%u) > %s(%u)",                             \
                #_field, (u4)(_field), #_limit, (u4)(_limit));              \
            return 0;                                                       \
        }                                                                   \
    }

#define SWAP_INDEX2(_field, _limit) {                                       \
        SWAP_FIELD2((_field));                                              \
        CHECK_INDEX((_field), (_limit));                                    \
    }

#define CHECK_INDEX_OR_NOINDEX(_field, _limit) {                            \
        if ((_field) != kDexNoIndex && (_field) >= (_limit)) {              \
            fprintf(stderr, "Bad index: %s(%u) > %s(%u)",                             \
                #_field, (u4)(_field), #_limit, (u4)(_limit));              \
            return 0;                                                       \
        }                                                                   \
    }

#define SWAP_INDEX4(_field, _limit) {                                       \
        SWAP_FIELD4((_field));                                              \
        CHECK_INDEX((_field), (_limit));                                    \
    }

#define SWAP_INDEX4_OR_NOINDEX(_field, _limit) {                            \
        SWAP_FIELD4((_field));                                              \
        CHECK_INDEX_OR_NOINDEX((_field), (_limit));                         \
    }

static u4 readUnsignedLittleEndian(const CheckState* state, const u1** pData,
        u4 size) {
    const u1* data = *pData;
    u4 result = 0;
    u4 i;

    CHECK_PTR_RANGE(data, data + size);

    for (i = 0; i < size; i++) {
        result |= ((u4) *(data++)) << (i * 8);
    }

    *pData = data;
    return result;
}

static bool swapDexHeader(const CheckState* state, DexHeader* pHeader)
{
    CHECK_PTR_RANGE(pHeader, pHeader + 1);

    // magic is ok
    SWAP_FIELD4(pHeader->checksum);
    // signature is ok
    SWAP_FIELD4(pHeader->fileSize);
    SWAP_FIELD4(pHeader->headerSize);
    SWAP_FIELD4(pHeader->endianTag);
    SWAP_FIELD4(pHeader->linkSize);
    SWAP_OFFSET4(pHeader->linkOff);
    SWAP_OFFSET4(pHeader->mapOff);
    SWAP_FIELD4(pHeader->stringIdsSize);
    SWAP_OFFSET4(pHeader->stringIdsOff);
    SWAP_FIELD4(pHeader->typeIdsSize);
    SWAP_OFFSET4(pHeader->typeIdsOff);
    SWAP_FIELD4(pHeader->fieldIdsSize);
    SWAP_OFFSET4(pHeader->fieldIdsOff);
    SWAP_FIELD4(pHeader->methodIdsSize);
    SWAP_OFFSET4(pHeader->methodIdsOff);
    SWAP_FIELD4(pHeader->protoIdsSize);
    SWAP_OFFSET4(pHeader->protoIdsOff);
    SWAP_FIELD4(pHeader->classDefsSize);
    SWAP_OFFSET4(pHeader->classDefsOff);
    SWAP_FIELD4(pHeader->dataSize);
    SWAP_OFFSET4(pHeader->dataOff);

    if (pHeader->endianTag != kDexEndianConstant) {
        fprintf(stderr, "Unexpected endian_tag: %#x", pHeader->endianTag);
        return false;
    }

    // Assign variables so the diagnostic is prettier. (Hooray for macros.)
    u4 linkOff = pHeader->linkOff;
    u4 linkEnd = linkOff + pHeader->linkSize;
    u4 dataOff = pHeader->dataOff;
    u4 dataEnd = dataOff + pHeader->dataSize;
    CHECK_OFFSET_RANGE(linkOff, linkEnd);
    CHECK_OFFSET_RANGE(dataOff, dataEnd);

    /*
     * Note: The offsets and ranges of the other header items end up getting
     * checked during the first iteration over the map.
     */

    return true;
}

static size_t calcDefinedClassBitsSize(const CheckState* state)
{
    // Divide typeIdsSize by 32 (0x20), rounding up.
    return (state->pHeader->typeIdsSize + 0x1f) >> 5;
}

static bool setDefinedClassBit(const CheckState* state, u4 typeIdx) {
    u4 arrayIdx = typeIdx >> 5;
    u4 bit = 1 << (typeIdx & 0x1f);
    u4* element = &state->pDefinedClassBits[arrayIdx];
    bool result = (*element & bit) != 0;

    *element |= bit;

    return result;
}

static const char* primitiveTypeLabel(char typeChar)
{
    switch (typeChar) {
    case 'B':   return "byte";
    case 'C':   return "char";
    case 'D':   return "double";
    case 'F':   return "float";
    case 'I':   return "int";
    case 'J':   return "long";
    case 'S':   return "short";
    case 'V':   return "void";
    case 'Z':   return "boolean";
    default:
                return "UNKNOWN";
    }
}

static char* descriptorToDot(const char* str)
{
    int targetLen = strlen(str);
    int offset = 0;
    int arrayDepth = 0;
    char* newStr;

    /* strip leading [s; will be added to end */
    while (targetLen > 1 && str[offset] == '[') {
        offset++;
        targetLen--;
    }
    arrayDepth = offset;

    if (targetLen == 1) {
        /* primitive type */
        str = primitiveTypeLabel(str[offset]);
        offset = 0;
        targetLen = strlen(str);
    } else {
        /* account for leading 'L' and trailing ';' */
        if (targetLen >= 2 && str[offset] == 'L' &&
            str[offset+targetLen-1] == ';')
        {
            targetLen -= 2;
            offset++;
        }
    }

    newStr = (char*)malloc(targetLen + arrayDepth * 2 +1);

    /* copy class name over */
    int i;
    for (i = 0; i < targetLen; i++) {
        char ch = str[offset + i];
        newStr[i] = (ch == '/' || ch == '$') ? '.' : ch;
    }

    /* add the appropriate number of brackets for arrays */
    while (arrayDepth-- > 0) {
        newStr[i++] = '[';
        newStr[i++] = ']';
    }
    newStr[i] = '\0';
    //assert(i == targetLen + arrayDepth * 2);

    return newStr;
}

int dexUtf8Cmp(const char* s1, const char* s2) {
    for (;;) {
        if (*s1 == '\0') {
            if (*s2 == '\0') {
                return 0;
            }
            return -1;
        } else if (*s2 == '\0') {
            return 1;
        }

        int utf1 = dexGetUtf16FromUtf8(&s1);
        int utf2 = dexGetUtf16FromUtf8(&s2);
        int diff = utf1 - utf2;

        if (diff != 0) {
            return diff;
        }
    }
}

bool dexHasValidMagic(const DexHeader* pHeader) {
	const u1* magic = pHeader->magic;
	const u1* version = &magic[4];

	if (memcmp(magic, DEX_MAGIC, 4) != 0) {
		fprintf(stderr, "ERROR: unrecognized magic number (%02x %02x %02x %02x)", magic[0],
				magic[1], magic[2], magic[3]);
		return false;
	}

	if ((memcmp(version, DEX_MAGIC_VERS, 4) != 0)
			&& (memcmp(version, DEX_MAGIC_VERS_API_13, 4) != 0)) {
		/*
		 * Magic was correct, but this is an unsupported older or
		 * newer format variant.
		 */
		fprintf(stderr, "ERROR: unsupported dex version (%02x %02x %02x %02x)", version[0],
				version[1], version[2], version[3]);
		return false;
	}

	return true;
}

static u4 mapTypeToBitMask(int mapType) {
	switch (mapType) {
	case kDexTypeHeaderItem:
		return 1 << 0;
	case kDexTypeStringIdItem:
		return 1 << 1;
	case kDexTypeTypeIdItem:
		return 1 << 2;
	case kDexTypeProtoIdItem:
		return 1 << 3;
	case kDexTypeFieldIdItem:
		return 1 << 4;
	case kDexTypeMethodIdItem:
		return 1 << 5;
	case kDexTypeClassDefItem:
		return 1 << 6;
	case kDexTypeMapList:
		return 1 << 7;
	case kDexTypeTypeList:
		return 1 << 8;
	case kDexTypeAnnotationSetRefList:
		return 1 << 9;
	case kDexTypeAnnotationSetItem:
		return 1 << 10;
	case kDexTypeClassDataItem:
		return 1 << 11;
	case kDexTypeCodeItem:
		return 1 << 12;
	case kDexTypeStringDataItem:
		return 1 << 13;
	case kDexTypeDebugInfoItem:
		return 1 << 14;
	case kDexTypeAnnotationItem:
		return 1 << 15;
	case kDexTypeEncodedArrayItem:
		return 1 << 16;
	case kDexTypeAnnotationsDirectoryItem:
		return 1 << 17;
	default: {
		fprintf(stderr, "Unknown map item type %04x", mapType);
		return 0;
	}
	}
}

static bool isDataSectionType(int mapType) {
	switch (mapType) {
	case kDexTypeHeaderItem:
	case kDexTypeStringIdItem:
	case kDexTypeTypeIdItem:
	case kDexTypeProtoIdItem:
	case kDexTypeFieldIdItem:
	case kDexTypeMethodIdItem:
	case kDexTypeClassDefItem: {
		return false;
	}
	}

	return true;
}

static bool verifyUlebs(const u1* pData, const u1* pLimit, u4 count) {
	bool okay = true;
	u4 i;

	while (okay && (count-- != 0)) {
		readAndVerifyUnsignedLeb128(&pData, pLimit, &okay);
	}

	return okay;
}

void dexReadClassDataHeader(const u1** pData, DexClassDataHeader *pHeader) {
	pHeader->staticFieldsSize = readUnsignedLeb128(pData);
	pHeader->instanceFieldsSize = readUnsignedLeb128(pData);
	pHeader->directMethodsSize = readUnsignedLeb128(pData);
	pHeader->virtualMethodsSize = readUnsignedLeb128(pData);
}

bool dexReadAndVerifyClassDataHeader(const u1** pData, const u1* pLimit,
		DexClassDataHeader *pHeader) {
	if (!verifyUlebs(*pData, pLimit, 4)) {
		return false;
	}

	dexReadClassDataHeader(pData, pHeader);
	return true;
}

void dexReadClassDataField(const u1** pData, DexField* pField, u4* lastIndex) {
	u4 index = *lastIndex + readUnsignedLeb128(pData);

	pField->accessFlags = readUnsignedLeb128(pData);
	pField->fieldIdx = index;
	*lastIndex = index;
}

bool dexReadAndVerifyClassDataField(const u1** pData, const u1* pLimit,
		DexField* pField, u4* lastIndex) {
	if (!verifyUlebs(*pData, pLimit, 2)) {
		return false;
	}

	dexReadClassDataField(pData, pField, lastIndex);
	return true;
}

void dexReadClassDataMethod(const u1** pData, DexMethod* pMethod,
		u4* lastIndex) {
	u4 index = *lastIndex + readUnsignedLeb128(pData);

	pMethod->accessFlags = readUnsignedLeb128(pData);
	pMethod->codeOff = readUnsignedLeb128(pData);
	pMethod->methodIdx = index;
	*lastIndex = index;
}

bool dexReadAndVerifyClassDataMethod(const u1** pData, const u1* pLimit,
        DexMethod* pMethod, u4* lastIndex) {
    if (! verifyUlebs(*pData, pLimit, 3)) {
        return false;
    }

    dexReadClassDataMethod(pData, pMethod, lastIndex);
    return true;
}

DexClassData* dexReadAndVerifyClassData(const u1** pData, const u1* pLimit) {
	DexClassDataHeader header;
	u4 lastIndex;

	if (*pData == NULL) {
		DexClassData* result = (DexClassData*) malloc(sizeof(DexClassData));
		memset(result, 0, sizeof(*result));
		return result;
	}

	if (!dexReadAndVerifyClassDataHeader(pData, pLimit, &header)) {
		return NULL;
	}

	size_t resultSize = sizeof(DexClassData)
			+ (header.staticFieldsSize * sizeof(DexField))
			+ (header.instanceFieldsSize * sizeof(DexField))
			+ (header.directMethodsSize * sizeof(DexMethod))
			+ (header.virtualMethodsSize * sizeof(DexMethod));

	DexClassData* result = (DexClassData*) malloc(resultSize);
	u1* ptr = ((u1*) result) + sizeof(DexClassData);
	bool okay = true;
	u4 i;

	if (result == NULL) {
		return NULL;
	}

	result->header = header;

	if (header.staticFieldsSize != 0) {
		result->staticFields = (DexField*) ptr;
		ptr += header.staticFieldsSize * sizeof(DexField);
	} else {
		result->staticFields = NULL;
	}

	if (header.instanceFieldsSize != 0) {
		result->instanceFields = (DexField*) ptr;
		ptr += header.instanceFieldsSize * sizeof(DexField);
	} else {
		result->instanceFields = NULL;
	}

	if (header.directMethodsSize != 0) {
		result->directMethods = (DexMethod*) ptr;
		ptr += header.directMethodsSize * sizeof(DexMethod);
	} else {
		result->directMethods = NULL;
	}

	if (header.virtualMethodsSize != 0) {
		result->virtualMethods = (DexMethod*) ptr;
	} else {
		result->virtualMethods = NULL;
	}

	lastIndex = 0;
	for (i = 0; okay && (i < header.staticFieldsSize); i++) {
		okay = dexReadAndVerifyClassDataField(pData, pLimit,
				&result->staticFields[i], &lastIndex);
	}

	lastIndex = 0;
	for (i = 0; okay && (i < header.instanceFieldsSize); i++) {
		okay = dexReadAndVerifyClassDataField(pData, pLimit,
				&result->instanceFields[i], &lastIndex);
	}

	lastIndex = 0;
	for (i = 0; okay && (i < header.directMethodsSize); i++) {
		okay = dexReadAndVerifyClassDataMethod(pData, pLimit,
				&result->directMethods[i], &lastIndex);
	}

	lastIndex = 0;
	for (i = 0; okay && (i < header.virtualMethodsSize); i++) {
		okay = dexReadAndVerifyClassDataMethod(pData, pLimit,
				&result->virtualMethods[i], &lastIndex);
	}

	if (!okay) {
		free(result);
		return NULL;
	}

	return result;
}

static bool checkMapSection(const CheckState* state, u4 sectionOffset,
        u4 sectionCount, u4* endOffset) {
    if (sectionCount != 1) {
        fprintf(stderr, "Multiple map list items");
        return false;
    }

    if (sectionOffset != state->pHeader->mapOff) {
        fprintf(stderr, "Map not at header-defined offset: %#x, expected %#x",
                sectionOffset, state->pHeader->mapOff);
        return false;
    }

    const DexMapList* pMap = (const DexMapList*) filePointer(state, sectionOffset);

    *endOffset =
        sectionOffset + sizeof(u4) + (pMap->size * sizeof(DexMapItem));
    return true;
}

DexDataMap* dexDataMapAlloc(u4 maxCount) {
    /*
     * Allocate a single chunk for the DexDataMap per se as well as the
     * two arrays.
     */
    size_t size = 0;
    DexDataMap* map = NULL;

    /*
     * Avoiding pulling in safe_iop for safe_iopf.
     */
    if (!safe_mul(&size, maxCount, sizeof(u4) + sizeof(u2)) ||
        !safe_add(&size, size, sizeof(DexDataMap))) {
      return NULL;
    }

    map = (DexDataMap*) malloc(size);

    if (map == NULL) {
        return NULL;
    }

    map->count = 0;
    map->max = maxCount;
    map->offsets = (u4*) (map + 1);
    map->types = (u2*) (map->offsets + maxCount);

    return map;
}

int dexDataMapGet(DexDataMap* map, u4 offset) {
    assert(map != NULL);

    // Note: Signed type is important for max and min.
    int min = 0;
    int max = map->count - 1;
    u4* offsets = map->offsets;

    while (max >= min) {
        int guessIdx = (min + max) >> 1;
        u4 guess = offsets[guessIdx];

        if (offset < guess) {
            max = guessIdx - 1;
        } else if (offset > guess) {
            min = guessIdx + 1;
        } else {
            // We have a winner!
            return map->types[guessIdx];
        }
    }

    // No match.
    return -1;
}

bool dexDataMapVerify(DexDataMap* map, u4 offset, u2 type) {
    int found = dexDataMapGet(map, offset);

    if (found == type) {
        return true;
    }

    if (found < 0) {
        fprintf(stderr, "No data map entry found @ %#x; expected %x",
                offset, type);
    } else {
        fprintf(stderr, "Unexpected data map entry @ %#x: expected %x, found %x",
                offset, type, found);
    }

    return false;
}

static void* swapStringIdItem(const CheckState* state, void* ptr) {
    DexStringId* item = (DexStringId*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_OFFSET4(item->stringDataOff);

    return item + 1;
}

const char* dexGetStringData(const DexFile* pDexFile,
		const DexStringId* pStringId) {
	const u1* ptr = pDexFile->baseAddr + pStringId->stringDataOff;

	// Skip the uleb128 length.
	while (*(ptr++) > 0x7f)
		/* empty */;

	return (const char*) ptr;
}

static void* crossVerifyStringIdItem(const CheckState* state, void* ptr) {
    const DexStringId* item = (const DexStringId*) ptr;

    if (!dexDataMapVerify(state->pDataMap,
                    item->stringDataOff, kDexTypeStringDataItem)) {
        return NULL;
    }

    const DexStringId* item0 = (const DexStringId*) state->previousItem;
    if (item0 != NULL) {
        // Check ordering.
        const char* s0 = dexGetStringData(state->pDexFile, item0);
        const char* s1 = dexGetStringData(state->pDexFile, item);
        if (dexUtf8Cmp(s0, s1) >= 0) {
            fprintf(stderr, "Out-of-order string_ids: '%s' then '%s'", s0, s1);
            return NULL;
        }
    }

    return (void*) (item + 1);
}

static void* swapTypeIdItem(const CheckState* state, void* ptr) {
    DexTypeId* item = (DexTypeId*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_INDEX4(item->descriptorIdx, state->pHeader->stringIdsSize);

    return item + 1;
}


static void* swapProtoIdItem(const CheckState* state, void* ptr) {
    DexProtoId* item = (DexProtoId*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_INDEX4(item->shortyIdx, state->pHeader->stringIdsSize);
    SWAP_INDEX4(item->returnTypeIdx, state->pHeader->typeIdsSize);
    SWAP_OFFSET4(item->parametersOff);

    return item + 1;
}

static void* swapFieldIdItem(const CheckState* state, void* ptr) {
    DexFieldId* item = (DexFieldId*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_INDEX2(item->classIdx, state->pHeader->typeIdsSize);
    SWAP_INDEX2(item->typeIdx, state->pHeader->typeIdsSize);
    SWAP_INDEX4(item->nameIdx, state->pHeader->stringIdsSize);

    return item + 1;
}



static void* swapMethodIdItem(const CheckState* state, void* ptr) {
    DexMethodId* item = (DexMethodId*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_INDEX2(item->classIdx, state->pHeader->typeIdsSize);
    SWAP_INDEX2(item->protoIdx, state->pHeader->protoIdsSize);
    SWAP_INDEX4(item->nameIdx, state->pHeader->stringIdsSize);

    return item + 1;
}

static void* swapClassDefItem(const CheckState* state, void* ptr) {
    DexClassDef* item = (DexClassDef*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_INDEX4(item->classIdx, state->pHeader->typeIdsSize);
    SWAP_FIELD4(item->accessFlags);
    SWAP_INDEX4_OR_NOINDEX(item->superclassIdx, state->pHeader->typeIdsSize);
    SWAP_OFFSET4(item->interfacesOff);
    SWAP_INDEX4_OR_NOINDEX(item->sourceFileIdx, state->pHeader->stringIdsSize);
    SWAP_OFFSET4(item->annotationsOff);
    SWAP_OFFSET4(item->classDataOff);

    if ((item->accessFlags & ~ACC_CLASS_MASK) != 0) {
        // The VM specification says that unknown flags should be ignored.
        fprintf(stderr, "Bogus class access flags %x", item->accessFlags);
        item->accessFlags &= ACC_CLASS_MASK;
    }

    return item + 1;
}

static void* swapTypeList(const CheckState* state, void* ptr)
{
    DexTypeList* pTypeList = (DexTypeList*) ptr;
    DexTypeItem* pType;
    u4 count;

    CHECK_PTR_RANGE(pTypeList, pTypeList + 1);
    SWAP_FIELD4(pTypeList->size);
    count = pTypeList->size;
    pType = pTypeList->list;
    CHECK_LIST_SIZE(pType, count, sizeof(DexTypeItem));

    while (count--) {
        SWAP_INDEX2(pType->typeIdx, state->pHeader->typeIdsSize);
        pType++;
    }

    return pType;
}

static void* swapAnnotationSetRefList(const CheckState* state, void* ptr) {
    DexAnnotationSetRefList* list = (DexAnnotationSetRefList*) ptr;
    DexAnnotationSetRefItem* item;
    u4 count;

    CHECK_PTR_RANGE(list, list + 1);
    SWAP_FIELD4(list->size);
    count = list->size;
    item = list->list;
    CHECK_LIST_SIZE(item, count, sizeof(DexAnnotationSetRefItem));

    while (count--) {
        SWAP_OFFSET4(item->annotationsOff);
        item++;
    }

    return item;
}

static void* swapAnnotationSetItem(const CheckState* state, void* ptr) {
    DexAnnotationSetItem* set = (DexAnnotationSetItem*) ptr;
    u4* item;
    u4 count;

    CHECK_PTR_RANGE(set, set + 1);
    SWAP_FIELD4(set->size);
    count = set->size;
    item = set->entries;
    CHECK_LIST_SIZE(item, count, sizeof(u4));

    while (count--) {
        SWAP_OFFSET4(*item);
        item++;
    }

    return item;
}

const DexTry* dexGetTries(const DexCode* pCode) {
	const u2* insnsEnd = &pCode->insns[pCode->insnsSize];

	if ((((uintptr_t) insnsEnd) & 3) != 0) {
		insnsEnd++;
	}

	return (const DexTry*) insnsEnd;
}

const u1* dexGetCatchHandlerData(const DexCode* pCode) {
	const DexTry* pTries = dexGetTries(pCode);
	return (const u1*) &pTries[pCode->triesSize];
}

static u4 setHandlerOffsAndVerify(const CheckState* state,
        DexCode* code, u4 firstOffset, u4 handlersSize, u4* handlerOffs) {
    const u1* fileEnd = state->fileEnd;
    const u1* handlersBase = dexGetCatchHandlerData(code);
    u4 offset = firstOffset;
    bool okay = true;
    u4 i;

    for (i = 0; i < handlersSize; i++) {
        const u1* ptr = handlersBase + offset;
        int size = readAndVerifySignedLeb128(&ptr, fileEnd, &okay);
        bool catchAll;

        if (!okay) {
            fprintf(stderr, "Bogus size");
            return 0;
        }

        if ((size < -65536) || (size > 65536)) {
            fprintf(stderr, "Invalid size: %d", size);
            return 0;
        }

        if (size <= 0) {
            catchAll = true;
            size = -size;
        } else {
            catchAll = false;
        }

        handlerOffs[i] = offset;

        while (size-- > 0) {
            u4 typeIdx =
                readAndVerifyUnsignedLeb128(&ptr, fileEnd, &okay);

            if (!okay) {
                fprintf(stderr, "Bogus type_idx");
                return 0;
            }

            CHECK_INDEX(typeIdx, state->pHeader->typeIdsSize);

            u4 addr = readAndVerifyUnsignedLeb128(&ptr, fileEnd, &okay);

            if (!okay) {
                fprintf(stderr, "Bogus addr");
                return 0;
            }

            if (addr >= code->insnsSize) {
                fprintf(stderr, "Invalid addr: %#x", addr);
                return 0;
            }
        }

        if (catchAll) {
            u4 addr = readAndVerifyUnsignedLeb128(&ptr, fileEnd, &okay);

            if (!okay) {
                fprintf(stderr, "Bogus catch_all_addr");
                return 0;
            }

            if (addr >= code->insnsSize) {
                fprintf(stderr, "Invalid catch_all_addr: %#x", addr);
                return 0;
            }
        }

        offset = ptr - handlersBase;
    }

    return offset;
}

static void* swapTriesAndCatches(const CheckState* state, DexCode* code) {
    const u1* encodedHandlers = dexGetCatchHandlerData(code);
    const u1* encodedPtr = encodedHandlers;
    bool okay = true;
    u4 handlersSize =
        readAndVerifyUnsignedLeb128(&encodedPtr, state->fileEnd, &okay);

    if (!okay) {
        fprintf(stderr, "Bogus handlers_size");
        return NULL;
    }

    if ((handlersSize == 0) || (handlersSize >= 65536)) {
        fprintf(stderr, "Invalid handlers_size: %d", handlersSize);
        return NULL;
    }

    u4 handlerOffs[handlersSize]; // list of valid handlerOff values
    u4 endOffset = setHandlerOffsAndVerify(state, code,
            encodedPtr - encodedHandlers,
            handlersSize, handlerOffs);

    if (endOffset == 0) {
        return NULL;
    }

    DexTry* tries = (DexTry*) dexGetTries(code);
    u4 count = code->triesSize;
    u4 lastEnd = 0;

    CHECK_LIST_SIZE(tries, count, sizeof(DexTry));

    while (count--) {
        u4 i;

        SWAP_FIELD4(tries->startAddr);
        SWAP_FIELD2(tries->insnCount);
        SWAP_FIELD2(tries->handlerOff);

        if (tries->startAddr < lastEnd) {
            fprintf(stderr, "Out-of-order try");
            return NULL;
        }

        if (tries->startAddr >= code->insnsSize) {
            fprintf(stderr, "Invalid start_addr: %#x", tries->startAddr);
            return NULL;
        }

        for (i = 0; i < handlersSize; i++) {
            if (tries->handlerOff == handlerOffs[i]) {
                break;
            }
        }

        if (i == handlersSize) {
            fprintf(stderr, "Bogus handler offset: %#x", tries->handlerOff);
            return NULL;
        }

        lastEnd = tries->startAddr + tries->insnCount;

        if (lastEnd > code->insnsSize) {
            fprintf(stderr, "Invalid insn_count: %#x (end addr %#x)",
                    tries->insnCount, lastEnd);
            return NULL;
        }

        tries++;
    }

    return (u1*) encodedHandlers + endOffset;
}

static void* swapCodeItem(const CheckState* state, void* ptr) {
    DexCode* item = (DexCode*) ptr;
    u2* insns;
    u4 count;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_FIELD2(item->registersSize);
    SWAP_FIELD2(item->insSize);
    SWAP_FIELD2(item->outsSize);
    SWAP_FIELD2(item->triesSize);
    SWAP_OFFSET4(item->debugInfoOff);
    SWAP_FIELD4(item->insnsSize);

    if (item->insSize > item->registersSize) {
        fprintf(stderr, "insSize (%u) > registersSize (%u)", item->insSize,
                item->registersSize);
        return NULL;
    }

    if ((item->outsSize > 5) && (item->outsSize > item->registersSize)) {
        /*
         * It's okay for outsSize to be up to five, even if registersSize
         * is smaller, since the short forms of method invocation allow
         * repetition of a register multiple times within a single parameter
         * list. Longer parameter lists, though, need to be represented
         * in-order in the register file.
         */
        fprintf(stderr, "outsSize (%u) > registersSize (%u)", item->outsSize,
                item->registersSize);
        return NULL;
    }

    count = item->insnsSize;
    insns = item->insns;
    CHECK_LIST_SIZE(insns, count, sizeof(u2));

    while (count--) {
        *insns = SWAP2(*insns);
        insns++;
    }

    if (item->triesSize == 0) {
        ptr = insns;
    } else {
        if ((((uintptr_t) insns) & 3) != 0) {
            // Four-byte alignment for the tries. Verify the spacer is a 0.
            if (*insns != 0) {
                fprintf(stderr, "Non-zero padding: %#x", (u4) *insns);
                return NULL;
            }
        }

        ptr = swapTriesAndCatches(state, item);
    }

    return ptr;
}

static u1* swapFieldAnnotations(const CheckState* state, u4 count, u1* addr) {
    DexFieldAnnotationsItem* item = (DexFieldAnnotationsItem*) addr;
    bool first = true;
    u4 lastIdx = 0;

    CHECK_LIST_SIZE(item, count, sizeof(DexFieldAnnotationsItem));

    while (count--) {
        SWAP_INDEX4(item->fieldIdx, state->pHeader->fieldIdsSize);
        SWAP_OFFSET4(item->annotationsOff);

        if (first) {
            first = false;
        } else if (lastIdx >= item->fieldIdx) {
            fprintf(stderr, "Out-of-order field_idx: %#x then %#x", lastIdx,
                 item->fieldIdx);
            return NULL;
        }

        lastIdx = item->fieldIdx;
        item++;
    }

    return (u1*) item;
}

static u1* swapMethodAnnotations(const CheckState* state, u4 count, u1* addr) {
    DexMethodAnnotationsItem* item = (DexMethodAnnotationsItem*) addr;
    bool first = true;
    u4 lastIdx = 0;

    CHECK_LIST_SIZE(item, count, sizeof(DexMethodAnnotationsItem));

    while (count--) {
        SWAP_INDEX4(item->methodIdx, state->pHeader->methodIdsSize);
        SWAP_OFFSET4(item->annotationsOff);

        if (first) {
            first = false;
        } else if (lastIdx >= item->methodIdx) {
            fprintf(stderr, "Out-of-order method_idx: %#x then %#x", lastIdx,
                 item->methodIdx);
            return NULL;
        }

        lastIdx = item->methodIdx;
        item++;
    }

    return (u1*) item;
}

static u1* swapParameterAnnotations(const CheckState* state, u4 count,
        u1* addr) {
    DexParameterAnnotationsItem* item = (DexParameterAnnotationsItem*) addr;
    bool first = true;
    u4 lastIdx = 0;

    CHECK_LIST_SIZE(item, count, sizeof(DexParameterAnnotationsItem));

    while (count--) {
        SWAP_INDEX4(item->methodIdx, state->pHeader->methodIdsSize);
        SWAP_OFFSET4(item->annotationsOff);

        if (first) {
            first = false;
        } else if (lastIdx >= item->methodIdx) {
            fprintf(stderr, "Out-of-order method_idx: %#x then %#x", lastIdx,
                 item->methodIdx);
            return NULL;
        }

        lastIdx = item->methodIdx;
        item++;
    }

    return (u1*) item;
}

static void* swapAnnotationsDirectoryItem(const CheckState* state, void* ptr) {
    DexAnnotationsDirectoryItem* item = (DexAnnotationsDirectoryItem*) ptr;

    CHECK_PTR_RANGE(item, item + 1);
    SWAP_OFFSET4(item->classAnnotationsOff);
    SWAP_FIELD4(item->fieldsSize);
    SWAP_FIELD4(item->methodsSize);
    SWAP_FIELD4(item->parametersSize);

    u1* addr = (u1*) (item + 1);

    if (item->fieldsSize != 0) {
        addr = swapFieldAnnotations(state, item->fieldsSize, addr);
        if (addr == NULL) {
            return NULL;
        }
    }

    if (item->methodsSize != 0) {
        addr = swapMethodAnnotations(state, item->methodsSize, addr);
        if (addr == NULL) {
            return NULL;
        }
    }

    if (item->parametersSize != 0) {
        addr = swapParameterAnnotations(state, item->parametersSize, addr);
        if (addr == NULL) {
            return NULL;
        }
    }

    return addr;
}

const DexFieldAnnotationsItem* dexGetFieldAnnotations(
    const DexFile* pDexFile, const DexAnnotationsDirectoryItem* pAnnoDir)
{
    if (pAnnoDir->fieldsSize == 0)
        return NULL;

    // Skip past the header to the start of the field annotations.
    return (const DexFieldAnnotationsItem*) &pAnnoDir[1];
}

const DexMethodAnnotationsItem* dexGetMethodAnnotations(
    const DexFile* pDexFile, const DexAnnotationsDirectoryItem* pAnnoDir)
{
    if (pAnnoDir->methodsSize == 0)
        return NULL;

    /*
     * Skip past the header and field annotations to the start of the
     * method annotations.
     */
    const u1* addr = (const u1*) &pAnnoDir[1];
    addr += pAnnoDir->fieldsSize * sizeof (DexFieldAnnotationsItem);
    return (const DexMethodAnnotationsItem*) addr;
}

const DexParameterAnnotationsItem* dexGetParameterAnnotations(
    const DexFile* pDexFile, const DexAnnotationsDirectoryItem* pAnnoDir)
{
    if (pAnnoDir->parametersSize == 0)
        return NULL;

    /*
     * Skip past the header, field annotations, and method annotations
     * to the start of the parameter annotations.
     */
    const u1* addr = (const u1*) &pAnnoDir[1];
    addr += pAnnoDir->fieldsSize * sizeof (DexFieldAnnotationsItem);
    addr += pAnnoDir->methodsSize * sizeof (DexMethodAnnotationsItem);
    return (const DexParameterAnnotationsItem*) addr;
}

static bool verifyFields(const CheckState* state, u4 size,
        DexField* fields, bool expectStatic) {
    u4 i;

    for (i = 0; i < size; i++) {
        DexField* field = &fields[i];
        u4 accessFlags = field->accessFlags;
        bool isStatic = (accessFlags & ACC_STATIC) != 0;

        CHECK_INDEX(field->fieldIdx, state->pHeader->fieldIdsSize);

        if (isStatic != expectStatic) {
            fprintf(stderr, "Field in wrong list @ %d", i);
            return false;
        }

        if ((accessFlags & ~ACC_FIELD_MASK) != 0) {
            // The VM specification says that unknown flags should be ignored.
            fprintf(stderr, "Bogus field access flags %x @ %d", accessFlags, i);
            field->accessFlags &= ACC_FIELD_MASK;
        }
    }

    return true;
}

static bool verifyMethods(const CheckState* state, u4 size,
        DexMethod* methods, bool expectDirect) {
    u4 i;

    for (i = 0; i < size; i++) {
        DexMethod* method = &methods[i];

        CHECK_INDEX(method->methodIdx, state->pHeader->methodIdsSize);

        u4 accessFlags = method->accessFlags;
        bool isDirect =
            (accessFlags & (ACC_STATIC | ACC_PRIVATE | ACC_CONSTRUCTOR)) != 0;
        bool expectCode = (accessFlags & (ACC_NATIVE | ACC_ABSTRACT)) == 0;
        bool isSynchronized = (accessFlags & ACC_SYNCHRONIZED) != 0;
        bool allowSynchronized = (accessFlags & ACC_NATIVE) != 0;

        if (isDirect != expectDirect) {
            fprintf(stderr, "Method in wrong list @ %d", i);
            return false;
        }

        if (isSynchronized && !allowSynchronized) {
            fprintf(stderr, "Bogus method access flags (synchronization) %x @ %d", accessFlags, i);
            return false;
        }

        if ((accessFlags & ~ACC_METHOD_MASK) != 0) {
            // The VM specification says that unknown flags should be ignored.
            fprintf(stderr, "Bogus method access flags %x @ %d", accessFlags, i);
            method->accessFlags &= ACC_METHOD_MASK;
        }

        if (expectCode) {
            if (method->codeOff == 0) {
                fprintf(stderr, "Unexpected zero code_off for access_flags %x",
                        accessFlags);
                return false;
            }
        } else if (method->codeOff != 0) {
            fprintf(stderr, "Unexpected non-zero code_off %#x for access_flags %x",
                    method->codeOff, accessFlags);
            return false;
        }
    }

    return true;
}

const DexTypeId* dexGetTypeId(const DexFile* pDexFile, u4 idx) {
	assert(idx < pDexFile->pHeader->typeIdsSize);
	return &pDexFile->pTypeIds[idx];
}

const DexStringId* dexGetStringId(const DexFile* pDexFile, u4 idx) {
	assert(idx < pDexFile->pHeader->stringIdsSize);
	return &pDexFile->pStringIds[idx];
}

u4 dexGetAnnotationOff(
    const DexAnnotationSetItem* pAnnoSet, u4 idx)
{
    assert(idx < pAnnoSet->size);
    return pAnnoSet->entries[idx];
}

const DexAnnotationItem* dexGetAnnotationItem(
    const DexFile* pDexFile, const DexAnnotationSetItem* pAnnoSet, u4 idx)
{
    u4 offset = dexGetAnnotationOff(pAnnoSet, idx);
    if (offset == 0) {
        return NULL;
    }
    return (const DexAnnotationItem*) (pDexFile->baseAddr + offset);
}

const char* dexStringById(const DexFile* pDexFile, u4 idx) {
	const DexStringId* pStringId = dexGetStringId(pDexFile, idx);
	return dexGetStringData(pDexFile, pStringId);
}

const char* dexStringByTypeIdx(const DexFile* pDexFile, u4 idx) {
	const DexTypeId* typeId = dexGetTypeId(pDexFile, idx);
	return dexStringById(pDexFile, typeId->descriptorIdx);
}

static const u1* verifyEncodedAnnotation(const CheckState* state,
        const u1* data, bool crossVerify);

static const u1* verifyEncodedArray(const CheckState* state,
        const u1* data, bool crossVerify);

static const u1* verifyEncodedValue(const CheckState* state,
        const u1* data, bool crossVerify) {
    CHECK_PTR_RANGE(data, data + 1);

    u1 headerByte = *(data++);
    u4 valueType = headerByte & kDexAnnotationValueTypeMask;
    u4 valueArg = headerByte >> kDexAnnotationValueArgShift;

    switch (valueType) {
        case kDexAnnotationByte: {
            if (valueArg != 0) {
                fprintf(stderr, "Bogus byte size %#x", valueArg);
                return NULL;
            }
            data++;
            break;
        }
        case kDexAnnotationShort:
        case kDexAnnotationChar: {
            if (valueArg > 1) {
                fprintf(stderr, "Bogus char/short size %#x", valueArg);
                return NULL;
            }
            data += valueArg + 1;
            break;
        }
        case kDexAnnotationInt:
        case kDexAnnotationFloat: {
            if (valueArg > 3) {
                fprintf(stderr, "Bogus int/float size %#x", valueArg);
                return NULL;
            }
            data += valueArg + 1;
            break;
        }
        case kDexAnnotationLong:
        case kDexAnnotationDouble: {
            data += valueArg + 1;
            break;
        }
        case kDexAnnotationString: {
            if (valueArg > 3) {
                fprintf(stderr, "Bogus string size %#x", valueArg);
                return NULL;
            }
            u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
            CHECK_INDEX(idx, state->pHeader->stringIdsSize);
            break;
        }
        case kDexAnnotationType: {
            if (valueArg > 3) {
                fprintf(stderr, "Bogus type size %#x", valueArg);
                return NULL;
            }
            u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
            CHECK_INDEX(idx, state->pHeader->typeIdsSize);
            break;
        }
        case kDexAnnotationField:
        case kDexAnnotationEnum: {
            if (valueArg > 3) {
                fprintf(stderr, "Bogus field/enum size %#x", valueArg);
                return NULL;
            }
            u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
            CHECK_INDEX(idx, state->pHeader->fieldIdsSize);
            break;
        }
        case kDexAnnotationMethod: {
            if (valueArg > 3) {
                fprintf(stderr, "Bogus method size %#x", valueArg);
                return NULL;
            }
            u4 idx = readUnsignedLittleEndian(state, &data, valueArg + 1);
            CHECK_INDEX(idx, state->pHeader->methodIdsSize);
            break;
        }
        case kDexAnnotationArray: {
            if (valueArg != 0) {
                fprintf(stderr, "Bogus array value_arg %#x", valueArg);
                return NULL;
            }
            data = verifyEncodedArray(state, data, crossVerify);
            break;
        }
        case kDexAnnotationAnnotation: {
            if (valueArg != 0) {
                fprintf(stderr, "Bogus annotation value_arg %#x", valueArg);
                return NULL;
            }
            data = verifyEncodedAnnotation(state, data, crossVerify);
            break;
        }
        case kDexAnnotationNull: {
            if (valueArg != 0) {
                fprintf(stderr, "Bogus null value_arg %#x", valueArg);
                return NULL;
            }
            // Nothing else to do for this type.
            break;
        }
        case kDexAnnotationBoolean: {
            if (valueArg > 1) {
                fprintf(stderr, "Bogus boolean value_arg %#x", valueArg);
                return NULL;
            }
            // Nothing else to do for this type.
            break;
        }
        default: {
            fprintf(stderr, "Bogus value_type %#x", valueType);
            return NULL;
        }
    }

    return data;
}

static const u1* verifyEncodedArray(const CheckState* state,
        const u1* data, bool crossVerify) {
    bool okay = true;
    u4 size = readAndVerifyUnsignedLeb128(&data, state->fileEnd, &okay);

    if (!okay) {
        fprintf(stderr, "Bogus encoded_array size");
        return NULL;
    }

    while (size--) {
        data = verifyEncodedValue(state, data, crossVerify);
        if (data == NULL) {
            fprintf(stderr, "Bogus encoded_array value");
            return NULL;
        }
    }

    return data;
}

u4 DEX_MEMBER_VALID_LOW_ASCII[4] = { 0x00000000, // 00..1f low control characters; nothing valid
		0x03ff2010, // 20..3f digits and symbols; valid: '0'..'9', '$', '-'
		0x87fffffe, // 40..5f uppercase etc.; valid: 'A'..'Z', '_'
		0x07fffffe  // 60..7f lowercase etc.; valid: 'a'..'z'
		};

bool dexIsValidMemberNameUtf8_0(const char** pUtf8Ptr) {
	/*
	 * It's a multibyte encoded character. Decode it and analyze. We
	 * accept anything that isn't (a) an improperly encoded low value,
	 * (b) an improper surrogate pair, (c) an encoded '\0', (d) a high
	 * control character, or (e) a high space, layout, or special
	 * character (U+00a0, U+2000..U+200f, U+2028..U+202f,
	 * U+fff0..U+ffff). This is all specified in the dex format
	 * document.
	 */

	u2 utf16 = dexGetUtf16FromUtf8(pUtf8Ptr);

	// Perform follow-up tests based on the high 8 bits.
	switch (utf16 >> 8) {
	case 0x00: {
		// It's only valid if it's above the ISO-8859-1 high space (0xa0).
		return (utf16 > 0x00a0);
	}
	case 0xd8:
	case 0xd9:
	case 0xda:
	case 0xdb: {
		/*
		 * It's a leading surrogate. Check to see that a trailing
		 * surrogate follows.
		 */
		utf16 = dexGetUtf16FromUtf8(pUtf8Ptr);
		return (utf16 >= 0xdc00) && (utf16 <= 0xdfff);
	}
	case 0xdc:
	case 0xdd:
	case 0xde:
	case 0xdf: {
		// It's a trailing surrogate, which is not valid at this point.
		return false;
	}
	case 0x20:
	case 0xff: {
		// It's in the range that has spaces, controls, and specials.
		switch (utf16 & 0xfff8) {
		case 0x2000:
		case 0x2008:
		case 0x2028:
		case 0xfff0:
		case 0xfff8: {
			return false;
		}
		}
		break;
	}
	}

	return true;
}

bool dexIsValidMemberNameUtf8(const char** pUtf8Ptr) {
	u1 c = (u1) **pUtf8Ptr;
	if (c <= 0x7f) {
		// It's low-ascii, so check the table.
		u4 wordIdx = c >> 5;
		u4 bitIdx = c & 0x1f;
		(*pUtf8Ptr)++;
		return (DEX_MEMBER_VALID_LOW_ASCII[wordIdx] & (1 << bitIdx)) != 0;
	}

	/*
	 * It's a multibyte encoded character. Call a non-inline function
	 * for the heavy lifting.
	 */
	return dexIsValidMemberNameUtf8_0(pUtf8Ptr);
}

static bool isValidTypeDescriptorOrClassName(const char* s, bool isClassName,
		bool dotSeparator) {
	int arrayCount = 0;

	while (*s == '[') {
		arrayCount++;
		s++;
	}

	if (arrayCount > 255) {
		// Arrays may have no more than 255 dimensions.
		return false;
	}

	if (arrayCount != 0) {
		/*
		 * If we're looking at an array of some sort, then it doesn't
		 * matter if what is being asked for is a class name; the
		 * format looks the same as a type descriptor in that case, so
		 * treat it as such.
		 */
		isClassName = false;
	}

	if (!isClassName) {
		/*
		 * We are looking for a descriptor. Either validate it as a
		 * single-character primitive type, or continue on to check the
		 * embedded class name (bracketed by "L" and ";").
		 */
		switch (*(s++)) {
		case 'B':
		case 'C':
		case 'D':
		case 'F':
		case 'I':
		case 'J':
		case 'S':
		case 'Z': {
			// These are all single-character descriptors for primitive types.
			return (*s == '\0');
		}
		case 'V': {
			// Non-array void is valid, but you can't have an array of void.
			return (arrayCount == 0) && (*s == '\0');
		}
		case 'L': {
			// Class name: Break out and continue below.
			break;
		}
		default: {
			// Oddball descriptor character.
			return false;
		}
		}
	}

	/*
	 * We just consumed the 'L' that introduces a class name as part
	 * of a type descriptor, or we are looking for an unadorned class
	 * name.
	 */

	bool sepOrFirst = true; // first character or just encountered a separator.
	for (;;) {
		u1 c = (u1) *s;
		switch (c) {
		case '\0': {
			/*
			 * Premature end for a type descriptor, but valid for
			 * a class name as long as we haven't encountered an
			 * empty component (including the degenerate case of
			 * the empty string "").
			 */
			return isClassName && !sepOrFirst;
		}
		case ';': {
			/*
			 * Invalid character for a class name, but the
			 * legitimate end of a type descriptor. In the latter
			 * case, make sure that this is the end of the string
			 * and that it doesn't end with an empty component
			 * (including the degenerate case of "L;").
			 */
			return !isClassName && !sepOrFirst && (s[1] == '\0');
		}
		case '/':
		case '.': {
			if (dotSeparator != (c == '.')) {
				// The wrong separator character.
				return false;
			}
			if (sepOrFirst) {
				// Separator at start or two separators in a row.
				return false;
			}
			sepOrFirst = true;
			s++;
			break;
		}
		default: {
			if (!dexIsValidMemberNameUtf8(&s)) {
				return false;
			}
			sepOrFirst = false;
			break;
		}
		}
	}
}

bool dexIsValidTypeDescriptor(const char* s) {
	return isValidTypeDescriptorOrClassName(s, false, false);
}

bool dexIsClassDescriptor(const char* s) {
	if (!dexIsValidTypeDescriptor(s)) {
		return false;
	}

	return s[0] == 'L';
}

bool dexIsValidMemberName(const char* s) {
	bool angleName = false;

	switch (*s) {
	case '\0': {
		// The empty string is not a valid name.
		return false;
	}
	case '<': {
		/*
		 * '<' is allowed only at the start of a name, and if present,
		 * means that the name must end with '>'.
		 */
		angleName = true;
		s++;
		break;
	}
	}

	for (;;) {
		switch (*s) {
		case '\0': {
			return !angleName;
		}
		case '>': {
			return angleName && s[1] == '\0';
		}
		}
		if (!dexIsValidMemberNameUtf8(&s)) {
			return false;
		}
	}
}

static const u1* verifyEncodedAnnotation(const CheckState* state,
        const u1* data, bool crossVerify) {
    const u1* fileEnd = state->fileEnd;
    bool okay = true;
    u4 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);

    if (!okay) {
        fprintf(stderr, "Bogus encoded_annotation type_idx");
        return NULL;
    }

    CHECK_INDEX(idx, state->pHeader->typeIdsSize);

    if (crossVerify) {
        const char* descriptor = dexStringByTypeIdx(state->pDexFile, idx);
        if (!dexIsClassDescriptor(descriptor)) {
            fprintf(stderr, "Bogus annotation type: '%s'", descriptor);
            return NULL;
        }
    }

    u4 size = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
    u4 lastIdx = 0;
    bool first = true;

    if (!okay) {
        fprintf(stderr, "Bogus encoded_annotation size");
        return NULL;
    }

    while (size--) {
        idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);

        if (!okay) {
            fprintf(stderr, "Bogus encoded_annotation name_idx");
            return NULL;
        }

        CHECK_INDEX(idx, state->pHeader->stringIdsSize);

        if (crossVerify) {
            const char* name = dexStringById(state->pDexFile, idx);
            if (!dexIsValidMemberName(name)) {
                fprintf(stderr, "Bogus annotation member name: '%s'", name);
                return NULL;
            }
        }

        if (first) {
            first = false;
        } else if (lastIdx >= idx) {
            fprintf(stderr, "Out-of-order encoded_annotation name_idx: %#x then %#x",
                    lastIdx, idx);
            return NULL;
        }

        data = verifyEncodedValue(state, data, crossVerify);
        lastIdx = idx;

        if (data == NULL) {
            return NULL;
        }
    }

    return data;
}

static void* crossVerifyTypeIdItem(const CheckState* state, void* ptr) {
    const DexTypeId* item = (const DexTypeId*) ptr;
    const char* descriptor =
        dexStringById(state->pDexFile, item->descriptorIdx);

    if (!dexIsValidTypeDescriptor(descriptor)) {
        fprintf(stderr, "Invalid type descriptor: '%s'", descriptor);
        return NULL;
    }

    const DexTypeId* item0 = (const DexTypeId*) state->previousItem;
    if (item0 != NULL) {
        // Check ordering. This relies on string_ids being in order.
        if (item0->descriptorIdx >= item->descriptorIdx) {
            fprintf(stderr, "Out-of-order type_ids: %#x then %#x",
                    item0->descriptorIdx, item->descriptorIdx);
            return NULL;
        }
    }

    return (void*) (item + 1);
}

bool dexIsFieldDescriptor(const char* s) {
	if (!dexIsValidTypeDescriptor(s)) {
		return false;
	}

	return s[0] != 'V';
}

bool dexIsReferenceDescriptor(const char* s) {
	if (!dexIsValidTypeDescriptor(s)) {
		return false;
	}

	return (s[0] == 'L') || (s[0] == '[');
}

static void* crossVerifyFieldIdItem(const CheckState* state, void* ptr) {
    const DexFieldId* item = (const DexFieldId*) ptr;
    const char* s;

    s = dexStringByTypeIdx(state->pDexFile, item->classIdx);
    if (!dexIsClassDescriptor(s)) {
        fprintf(stderr, "Invalid descriptor for class_idx: '%s'", s);
        return NULL;
    }

    s = dexStringByTypeIdx(state->pDexFile, item->typeIdx);
    if (!dexIsFieldDescriptor(s)) {
        fprintf(stderr, "Invalid descriptor for type_idx: '%s'", s);
        return NULL;
    }

    s = dexStringById(state->pDexFile, item->nameIdx);
    if (!dexIsValidMemberName(s)) {
        fprintf(stderr, "Invalid name: '%s'", s);
        return NULL;
    }

    const DexFieldId* item0 = (const DexFieldId*) state->previousItem;
    if (item0 != NULL) {
        // Check ordering. This relies on the other sections being in order.
        bool done = false;
        bool bogus = false;

        if (item0->classIdx > item->classIdx) {
            bogus = true;
            done = true;
        } else if (item0->classIdx < item->classIdx) {
            done = true;
        }

        if (!done) {
            if (item0->nameIdx > item->nameIdx) {
                bogus = true;
                done = true;
            } else if (item0->nameIdx < item->nameIdx) {
                done = true;
            }
        }

        if (!done) {
            if (item0->typeIdx >= item->typeIdx) {
                bogus = true;
            }
        }

        if (bogus) {
            fprintf(stderr, "Out-of-order field_ids");
            return NULL;
        }
    }

    return (void*) (item + 1);
}

static void* crossVerifyMethodIdItem(const CheckState* state, void* ptr) {
    const DexMethodId* item = (const DexMethodId*) ptr;
    const char* s;

    s = dexStringByTypeIdx(state->pDexFile, item->classIdx);
    if (!dexIsReferenceDescriptor(s)) {
        fprintf(stderr, "Invalid descriptor for class_idx: '%s'", s);
        return NULL;
    }

    s = dexStringById(state->pDexFile, item->nameIdx);
    if (!dexIsValidMemberName(s)) {
        fprintf(stderr, "Invalid name: '%s'", s);
        return NULL;
    }

    const DexMethodId* item0 = (const DexMethodId*) state->previousItem;
    if (item0 != NULL) {
        // Check ordering. This relies on the other sections being in order.
        bool done = false;
        bool bogus = false;

        if (item0->classIdx > item->classIdx) {
            bogus = true;
            done = true;
        } else if (item0->classIdx < item->classIdx) {
            done = true;
        }

        if (!done) {
            if (item0->nameIdx > item->nameIdx) {
                bogus = true;
                done = true;
            } else if (item0->nameIdx < item->nameIdx) {
                done = true;
            }
        }

        if (!done) {
            if (item0->protoIdx >= item->protoIdx) {
                bogus = true;
            }
        }

        if (bogus) {
            fprintf(stderr, "Out-of-order method_ids");
            return NULL;
        }
    }

    return (void*) (item + 1);
}

void dexFileSetupBasicPointers(DexFile* pDexFile, const u1* data) {
	DexHeader *pHeader = (DexHeader*) data;

	pDexFile->baseAddr = data;
	pDexFile->pHeader = pHeader;
	pDexFile->pStringIds = (const DexStringId*) (data + pHeader->stringIdsOff);
	pDexFile->pTypeIds = (const DexTypeId*) (data + pHeader->typeIdsOff);
	pDexFile->pFieldIds = (const DexFieldId*) (data + pHeader->fieldIdsOff);
	pDexFile->pMethodIds = (const DexMethodId*) (data + pHeader->methodIdsOff);
	pDexFile->pProtoIds = (const DexProtoId*) (data + pHeader->protoIdsOff);
	pDexFile->pClassDefs = (const DexClassDef*) (data + pHeader->classDefsOff);
	pDexFile->pLinkData = (const DexLink*) (data + pHeader->linkOff);
}

const DexTypeList* dexGetProtoParameters(const DexFile *pDexFile,
		const DexProtoId* pProtoId) {
	if (pProtoId->parametersOff == 0) {
		return NULL;
	}
	return (const DexTypeList*) (pDexFile->baseAddr + pProtoId->parametersOff);
}

const DexTypeList* dexGetInterfacesList(const DexFile* pDexFile,
		const DexClassDef* pClassDef) {
	if (pClassDef->interfacesOff == 0)
		return NULL;
	return (const DexTypeList*) (pDexFile->baseAddr + pClassDef->interfacesOff);
}

const DexProtoId* dexGetProtoId(const DexFile* pDexFile, u4 idx) {
    assert(idx < pDexFile->pHeader->protoIdsSize);
    return &pDexFile->pProtoIds[idx];
}

static inline const DexProtoId* getProtoId(const DexProto* pProto) {
    return dexGetProtoId(pProto->dexFile, pProto->protoIdx);
}

void dexParameterIteratorInit(DexParameterIterator* pIterator,
		const DexProto* pProto) {
	pIterator->proto = pProto;
	pIterator->cursor = 0;

	pIterator->parameters = dexGetProtoParameters(pProto->dexFile,
			getProtoId(pProto));
	pIterator->parameterCount =
			(pIterator->parameters == NULL) ? 0 : pIterator->parameters->size;
}

const DexTypeItem* dexGetTypeItem(const DexTypeList* pList,
    u4 idx)
{
    assert(idx < pList->size);
    return &pList->list[idx];
}

u4 dexTypeListGetIdx(const DexTypeList* pList, u4 idx) {
	const DexTypeItem* pItem = dexGetTypeItem(pList, idx);
	return pItem->typeIdx;
}

u4 dexParameterIteratorNextIndex(DexParameterIterator* pIterator) {
	int cursor = pIterator->cursor;
	int parameterCount = pIterator->parameterCount;

	if (cursor >= parameterCount) {
		// The iteration is complete.
		return kDexNoIndex;
	} else {
		u4 idx = dexTypeListGetIdx(pIterator->parameters, cursor);
		pIterator->cursor++;
		return idx;
	}
}

const char* dexParameterIteratorNextDescriptor(
		DexParameterIterator* pIterator) {
	u4 idx = dexParameterIteratorNextIndex(pIterator);

	if (idx == kDexNoIndex) {
		return NULL;
	}

	return dexStringByTypeIdx(pIterator->proto->dexFile, idx);
}

const DexFieldId* dexGetFieldId(const DexFile* pDexFile, u4 idx) {
	assert(idx < pDexFile->pHeader->fieldIdsSize);
	return &pDexFile->pFieldIds[idx];
}

const DexMethodId* dexGetMethodId(const DexFile* pDexFile, u4 idx) {
	assert(idx < pDexFile->pHeader->methodIdsSize);
	return &pDexFile->pMethodIds[idx];
}

static bool isValidPointer(const void* ptr, const void* start, const void* end)
{
    return (ptr >= start) && (ptr < end) && (((uintptr_t) ptr & 7) == 0);
}

bool dexParseOptData(const u1* data, size_t length, DexFile* pDexFile)
{
    const void* pOptStart = data + pDexFile->pOptHeader->optOffset;
    const void* pOptEnd = data + length;
    const u4* pOpt = (const u4*) pOptStart;
    u4 optLength = (const u1*) pOptEnd - (const u1*) pOptStart;

    /*
     * Make sure the opt data start is in range and aligned. This may
     * seem like a superfluous check, but (a) if the file got
     * truncated, it might turn out that pOpt >= pOptEnd; and (b)
     * if the opt data header got corrupted, pOpt might not be
     * properly aligned. This test will catch both of these cases.
     */
     if (!isValidPointer(pOpt, pOptStart, pOptEnd)) {
        fprintf(stderr, "Bogus opt data start pointer");
        return false;
    }

    /* Make sure that the opt data length is a whole number of words. */
    if ((optLength & 3) != 0) {
        fprintf(stderr, "Unaligned opt data area end");
        return false;
    }

    /*
     * Make sure that the opt data area is large enough to have at least
     * one chunk header.
     */
    if (optLength < 8) {
        fprintf(stderr, "Undersized opt data area (%u)", optLength);
        return false;
    }

    /* Process chunks until we see the end marker. */
    while (*pOpt != kDexChunkEnd) {
        if (!isValidPointer(pOpt + 2, pOptStart, pOptEnd)) {
            fprintf(stderr, "Bogus opt data content pointer at offset %u",
                    ((const u1*) pOpt) - data);
            return false;
        }

        u4 size = *(pOpt + 1);
        const u1* pOptData = (const u1*) (pOpt + 2);

        /*
         * The rounded size is 64-bit aligned and includes +8 for the
         * type/size header (which was extracted immediately above).
         */
        u4 roundedSize = (size + 8 + 7) & ~7;
        const u4* pNextOpt = pOpt + (roundedSize / sizeof(u4));

        if (!isValidPointer(pNextOpt, pOptStart, pOptEnd)) {
            fprintf(stderr, "Opt data area problem for chunk of size %u at offset %u",
                    size, ((const u1*) pOpt) - data);
            return false;
        }

        switch (*pOpt) {
        case kDexChunkClassLookup:
            pDexFile->pClassLookup = (const DexClassLookup*) pOptData;
            break;
        case kDexChunkRegisterMaps:
            printf("+++ found register maps, size=%u", size);
            pDexFile->pRegisterMapPool = pOptData;
            break;
        default:
            printf("Unknown chunk 0x%08x (%c%c%c%c), size=%d in opt data area",
                *pOpt,
                (char) ((*pOpt) >> 24), (char) ((*pOpt) >> 16),
                (char) ((*pOpt) >> 8),  (char)  (*pOpt),
                size);
            break;
        }

        pOpt = pNextOpt;
    }

    return true;
}

u4 dexComputeChecksum(const DexHeader* pHeader)
{
    const u1* start = (const u1*) pHeader;

    uLong adler = adler32(0L, Z_NULL, 0);
    const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);

    return (u4) adler32(adler, start + nonSum, pHeader->fileSize - nonSum);
}

u4 dexComputeOptChecksum(const DexOptHeader* pOptHeader)
{
    const u1* start = (const u1*) pOptHeader + pOptHeader->depsOffset;
    const u1* end = (const u1*) pOptHeader +
        pOptHeader->optOffset + pOptHeader->optLength;

    uLong adler = adler32(0L, Z_NULL, 0);

    return (u4) adler32(adler, start, end - start);
}

void dexFileFree(DexFile* pDexFile)
{
    if (pDexFile == NULL)
        return;

    free(pDexFile);
}

DexFile* dexFileParse(const u1* data, size_t length, int flags)
{
    DexFile* pDexFile = NULL;
    const DexHeader* pHeader;
    const u1* magic;
    int result = -1;

    if (length < sizeof(DexHeader)) {
        fprintf(stderr, "too short to be a valid .dex");
        goto file_parse_bail;      /* bad file format */
    }

    pDexFile = (DexFile*) malloc(sizeof(DexFile));
    if (pDexFile == NULL)
        goto file_parse_bail;      /* alloc failure */
    memset(pDexFile, 0, sizeof(DexFile));

    if (memcmp(data, DEX_OPT_MAGIC, 4) == 0) {
        magic = data;
        if (memcmp(magic+4, DEX_OPT_MAGIC_VERS, 4) != 0) {
            fprintf(stderr, "bad opt version (0x%02x %02x %02x %02x)",
                 magic[4], magic[5], magic[6], magic[7]);
            goto file_parse_bail;
        }

        pDexFile->pOptHeader = (const DexOptHeader*) data;
        printf("Good opt header, DEX offset is %d, flags=0x%02x",
            pDexFile->pOptHeader->dexOffset, pDexFile->pOptHeader->flags);

        /* parse the optimized dex file tables */
        if (!dexParseOptData(data, length, pDexFile))
            goto file_parse_bail;

        /* ignore the opt header and appended data from here on out */
        data += pDexFile->pOptHeader->dexOffset;
        length -= pDexFile->pOptHeader->dexOffset;
        if (pDexFile->pOptHeader->dexLength > length) {
            fprintf(stderr, "File truncated? stored len=%d, rem len=%d",
                pDexFile->pOptHeader->dexLength, (int) length);
            goto file_parse_bail;
        }
        length = pDexFile->pOptHeader->dexLength;
    }

    dexFileSetupBasicPointers(pDexFile, data);
    pHeader = pDexFile->pHeader;

    if (!dexHasValidMagic(pHeader)) {
        goto file_parse_bail;
    }

    /*
     * Verify the checksum(s).  This is reasonably quick, but does require
     * touching every byte in the DEX file.  The base checksum changes after
     * byte-swapping and DEX optimization.
     */
    if (flags & kDexParseVerifyChecksum) {
		
		u4 adler = dexComputeChecksum(pHeader);
		if (adler != pHeader->checksum) {
			fprintf(stderr, "ERROR: bad checksum (%08x vs %08x)\n",
				adler, pHeader->checksum);
			if (!(flags & kDexParseContinueOnError))
				goto file_parse_bail;
		} else {
			printf("+++ adler32 checksum (%08x) verified\n", adler);
		}
		
		const DexOptHeader* pOptHeader = pDexFile->pOptHeader;
		if (pOptHeader != NULL) {
			adler = dexComputeOptChecksum(pOptHeader);
			if (adler != pOptHeader->checksum) {
				fprintf(stderr, "ERROR: bad opt checksum (%08x vs %08x)\n",
					adler, pOptHeader->checksum);
				if (!(flags & kDexParseContinueOnError))
					goto file_parse_bail;
			} else {
				printf("+++ adler32 opt checksum (%08x) verified\n", adler);
			}
		}
	}
		
	if (pHeader->fileSize != length) {
		fprintf(stderr, "ERROR: stored file size (%d) != expected (%d)\n",
			(int) pHeader->fileSize, (int) length);
		if (!(flags & kDexParseContinueOnError))
			goto file_parse_bail;
	}
		
	if (pHeader->classDefsSize == 0) {
		fprintf(stderr, "ERROR: DEX file has no classes in it, failing\n");
		goto file_parse_bail;
	}
		
	/*
	 * Success!
	 */
	result = 0;
		
file_parse_bail:
	if (result != 0 && pDexFile != NULL) {
		dexFileFree(pDexFile);
		pDexFile = NULL;
	}
	return pDexFile;
}

const DexClassDef* dexGetClassDef(const DexFile* pDexFile, u4 idx) {
    assert(idx < pDexFile->pHeader->classDefsSize);
    return &pDexFile->pClassDefs[idx];
}

const u1* dexGetClassData(const DexFile* pDexFile,
    const DexClassDef* pClassDef)
{
    if (pClassDef->classDataOff == 0)
        return NULL;
    return (const u1*) (pDexFile->baseAddr + pClassDef->classDataOff);
}

const DexCode* dexGetCode(const DexFile* pDexFile,
    const DexMethod* pDexMethod)
{
    if (pDexMethod->codeOff == 0)
        return NULL;
    return (const DexCode*) (pDexFile->baseAddr + pDexMethod->codeOff);
}

static int getFileStartAndLength(int fd, off_t *start_, size_t *length_)
{
    off_t start, end;
    size_t length;

    assert(start_ != NULL);
    assert(length_ != NULL);

    start = lseek(fd, 0L, SEEK_CUR);
    end = lseek(fd, 0L, SEEK_END);
    (void) lseek(fd, start, SEEK_SET);

    if (start == (off_t) -1 || end == (off_t) -1) {
        fprintf(stderr, "could not determine length of file");
        return -1;
    }

    length = end - start;
    if (length == 0) {
        fprintf(stderr, "file is empty");
        return -1;
    }

    *start_ = start;
    *length_ = length;

    return 0;
}

static bool swapMap(CheckState* state, DexMapList* pMap)
{
    DexMapItem* item = pMap->list;
    u4 count;
    u4 dataItemCount = 0; // Total count of items in the data section.
    u4 dataItemsLeft = state->pHeader->dataSize; // See use below.
    u4 usedBits = 0;      // Bit set: one bit per section
    bool first = true;
    u4 lastOffset = 0;

    SWAP_FIELD4(pMap->size);
    count = pMap->size;

    CHECK_LIST_SIZE(item, count, sizeof(DexMapItem));

    while (count--) {
        SWAP_FIELD2(item->type);
        SWAP_FIELD2(item->unused);
        SWAP_FIELD4(item->size);
        SWAP_OFFSET4(item->offset);

        if (first) {
            first = false;
        } else if (lastOffset >= item->offset) {
            fprintf(stderr, "Out-of-order map item: %#x then %#x",
                    lastOffset, item->offset);
            return false;
        }

        if (item->offset >= state->pHeader->fileSize) {
            fprintf(stderr, "Map item after end of file: %x, size %#x",
                    item->offset, state->pHeader->fileSize);
            return false;
        }

        if (isDataSectionType(item->type)) {
            u4 icount = item->size;

            /*
             * This sanity check on the data section items ensures that
             * there are no more items than the number of bytes in
             * the data section.
             */
            if (icount > dataItemsLeft) {
                fprintf(stderr, "Unrealistically many items in the data section: "
                        "at least %d", dataItemCount + icount);
                return false;
            }

            dataItemsLeft -= icount;
            dataItemCount += icount;
        }

        u4 bit = mapTypeToBitMask(item->type);

        if (bit == 0) {
            return false;
        }

        if ((usedBits & bit) != 0) {
            fprintf(stderr, "Duplicate map section of type %#x", item->type);
            return false;
        }

        usedBits |= bit;
        lastOffset = item->offset;
        item++;
    }

    if ((usedBits & mapTypeToBitMask(kDexTypeHeaderItem)) == 0) {
        fprintf(stderr, "Map is missing header entry");
        return false;
    }

    if ((usedBits & mapTypeToBitMask(kDexTypeMapList)) == 0) {
        fprintf(stderr, "Map is missing map_list entry");
        return false;
    }

    if (((usedBits & mapTypeToBitMask(kDexTypeStringIdItem)) == 0)
            && ((state->pHeader->stringIdsOff != 0)
                    || (state->pHeader->stringIdsSize != 0))) {
        fprintf(stderr, "Map is missing string_ids entry");
        return false;
    }

    if (((usedBits & mapTypeToBitMask(kDexTypeTypeIdItem)) == 0)
            && ((state->pHeader->typeIdsOff != 0)
                    || (state->pHeader->typeIdsSize != 0))) {
        fprintf(stderr, "Map is missing type_ids entry");
        return false;
    }

    if (((usedBits & mapTypeToBitMask(kDexTypeProtoIdItem)) == 0)
            && ((state->pHeader->protoIdsOff != 0)
                    || (state->pHeader->protoIdsSize != 0))) {
        fprintf(stderr, "Map is missing proto_ids entry");
        return false;
    }

    if (((usedBits & mapTypeToBitMask(kDexTypeFieldIdItem)) == 0)
            && ((state->pHeader->fieldIdsOff != 0)
                    || (state->pHeader->fieldIdsSize != 0))) {
        fprintf(stderr, "Map is missing field_ids entry");
        return false;
    }

    if (((usedBits & mapTypeToBitMask(kDexTypeMethodIdItem)) == 0)
            && ((state->pHeader->methodIdsOff != 0)
                    || (state->pHeader->methodIdsSize != 0))) {
        fprintf(stderr, "Map is missing method_ids entry");
        return false;
    }

    if (((usedBits & mapTypeToBitMask(kDexTypeClassDefItem)) == 0)
            && ((state->pHeader->classDefsOff != 0)
                    || (state->pHeader->classDefsSize != 0))) {
        fprintf(stderr, "Map is missing class_defs entry");
        return false;
    }

    state->pDataMap = dexDataMapAlloc(dataItemCount);
    if (state->pDataMap == NULL) {
        fprintf(stderr, "Unable to allocate data map (size %#x)", dataItemCount);
        return false;
    }

    return true;
}

static bool checkHeaderSection(const CheckState* state, u4 sectionOffset,
        u4 sectionCount, u4* endOffset) {
    if (sectionCount != 1) {
        fprintf(stderr, "Multiple header items");
        return false;
    }

    if (sectionOffset != 0) {
        fprintf(stderr, "Header at %#x; not at start of file", sectionOffset);
        return false;
    }

    const DexHeader* pHeader = (const DexHeader*) filePointer(state, 0);
    *endOffset = pHeader->headerSize;
    return true;
}

typedef void* ItemVisitorFunction(const CheckState* state, void* ptr);

void dexDataMapAdd(DexDataMap* map, u4 offset, u2 type) {
    assert(map != NULL);
    assert(map->count < map->max);

    if ((map->count != 0) &&
            (map->offsets[map->count - 1] >= offset)) {
        fprintf(stderr, "Out-of-order data map offset: %#x then %#x",
                map->offsets[map->count - 1], offset);
        return;
    }

    map->offsets[map->count] = offset;
    map->types[map->count] = type;
    map->count++;
}

static bool iterateSectionWithOptionalUpdate(CheckState* state,
        u4 offset, u4 count, ItemVisitorFunction* func, u4 alignment,
        u4* nextOffset, int mapType) {
    u4 alignmentMask = alignment - 1;
    u4 i;

    state->previousItem = NULL;

    for (i = 0; i < count; i++) {
        u4 newOffset = (offset + alignmentMask) & ~alignmentMask;
        u1* ptr = (u1*) filePointer(state, newOffset);

        if (offset < newOffset) {
            ptr = (u1*) filePointer(state, offset);
            if (offset < newOffset) {
                CHECK_OFFSET_RANGE(offset, newOffset);
                while (offset < newOffset) {
                    if (*ptr != '\0') {
                        fprintf(stderr, "Non-zero padding 0x%02x @ %x", *ptr, offset);
                        return false;
                    }
                    ptr++;
                    offset++;
                }
            }
        }

        u1* newPtr = (u1*) func(state, ptr);
        newOffset = fileOffset(state, newPtr);

        if (newPtr == NULL) {
            fprintf(stderr, "Trouble with item %d @ offset %#x", i, offset);
            return false;
        }

        if (newOffset > state->fileLen) {
            fprintf(stderr, "Item %d @ offset %#x ends out of bounds", i, offset);
            return false;
        }

        if (mapType >= 0) {
            dexDataMapAdd(state->pDataMap, offset, mapType);
        }

        state->previousItem = ptr;
        offset = newOffset;
    }

    if (nextOffset != NULL) {
        *nextOffset = offset;
    }

    return true;
}

static bool iterateSection(CheckState* state, u4 offset, u4 count,
        ItemVisitorFunction* func, u4 alignment, u4* nextOffset) {
    return iterateSectionWithOptionalUpdate(state, offset, count, func,
            alignment, nextOffset, -1);
}

static bool checkBoundsAndIterateSection(CheckState* state,
        u4 offset, u4 count, u4 expectedOffset, u4 expectedCount,
        ItemVisitorFunction* func, u4 alignment, u4* nextOffset) {
    if (offset != expectedOffset) {
        fprintf(stderr, "Bogus offset for section: got %#x; expected %#x",
                offset, expectedOffset);
        return false;
    }

    if (count != expectedCount) {
        fprintf(stderr, "Bogus size for section: got %#x; expected %#x",
                count, expectedCount);
        return false;
    }

    return iterateSection(state, offset, count, func, alignment, nextOffset);
}

static bool iterateDataSection(CheckState* state, u4 offset, u4 count,
        ItemVisitorFunction* func, u4 alignment, u4* nextOffset, int mapType) {
    u4 dataStart = state->pHeader->dataOff;
    u4 dataEnd = dataStart + state->pHeader->dataSize;

    assert(nextOffset != NULL);

    if ((offset < dataStart) || (offset >= dataEnd)) {
        fprintf(stderr, "Bogus offset for data subsection: %#x", offset);
        return false;
    }

    if (!iterateSectionWithOptionalUpdate(state, offset, count, func,
                    alignment, nextOffset, mapType)) {
        return false;
    }

    if (*nextOffset > dataEnd) {
        fprintf(stderr, "Out-of-bounds end of data subsection: %#x", *nextOffset);
        return false;
    }

    return true;
}

static bool verifyClassDataItem0(const CheckState* state,
        DexClassData* classData) {
    bool okay;

    okay = verifyFields(state, classData->header.staticFieldsSize,
            classData->staticFields, true);

    if (!okay) {
        fprintf(stderr, "Trouble with static fields");
        return false;
    }

    verifyFields(state, classData->header.instanceFieldsSize,
            classData->instanceFields, false);

    if (!okay) {
        fprintf(stderr, "Trouble with instance fields");
        return false;
    }

    okay = verifyMethods(state, classData->header.directMethodsSize,
            classData->directMethods, true);

    if (!okay) {
        fprintf(stderr, "Trouble with direct methods");
        return false;
    }

    okay = verifyMethods(state, classData->header.virtualMethodsSize,
            classData->virtualMethods, false);

    if (!okay) {
        fprintf(stderr, "Trouble with virtual methods");
        return false;
    }

    return true;
}

static void* intraVerifyClassDataItem(const CheckState* state, void* ptr) {
    const u1* data = (const u1*) ptr;
    DexClassData* classData = dexReadAndVerifyClassData(&data, state->fileEnd);

    if (classData == NULL) {
        fprintf(stderr, "Unable to parse class_data_item");
        return NULL;
    }

    bool okay = verifyClassDataItem0(state, classData);

    free(classData);

    if (!okay) {
        return NULL;
    }

    return (void*) data;
}

static void* intraVerifyStringDataItem(const CheckState* state, void* ptr) {
    const u1* fileEnd = state->fileEnd;
    const u1* data = (const u1*) ptr;
    bool okay = true;
    u4 utf16Size = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
    u4 i;

    if (!okay) {
        fprintf(stderr, "Bogus utf16_size");
        return NULL;
    }

    for (i = 0; i < utf16Size; i++) {
        if (data >= fileEnd) {
            fprintf(stderr, "String data would go beyond end-of-file");
            return NULL;
        }

        u1 byte1 = *(data++);

        // Switch on the high four bits.
        switch (byte1 >> 4) {
            case 0x00: {
                // Special case of bit pattern 0xxx.
                if (byte1 == 0) {
                    fprintf(stderr, "String shorter than indicated utf16_size %#x",
                            utf16Size);
                    return NULL;
                }
                break;
            }
            case 0x01:
            case 0x02:
            case 0x03:
            case 0x04:
            case 0x05:
            case 0x06:
            case 0x07: {
                // Bit pattern 0xxx. No need for any extra bytes or checks.
                break;
            }
            case 0x08:
            case 0x09:
            case 0x0a:
            case 0x0b:
            case 0x0f: {
                /*
                 * Bit pattern 10xx or 1111, which are illegal start bytes.
                 * Note: 1111 is valid for normal UTF-8, but not the
                 * modified UTF-8 used here.
                 */
                fprintf(stderr, "Illegal start byte %#x", byte1);
                return NULL;
            }
            case 0x0e: {
                // Bit pattern 1110, so there are two additional bytes.
                u1 byte2 = *(data++);
                if ((byte2 & 0xc0) != 0x80) {
                    fprintf(stderr, "Illegal continuation byte %#x", byte2);
                    return NULL;
                }
                u1 byte3 = *(data++);
                if ((byte3 & 0xc0) != 0x80) {
                    fprintf(stderr, "Illegal continuation byte %#x", byte3);
                    return NULL;
                }
                u2 value = ((byte1 & 0x0f) << 12) | ((byte2 & 0x3f) << 6)
                    | (byte3 & 0x3f);
                if (value < 0x800) {
                    fprintf(stderr, "Illegal representation for value %x", value);
                    return NULL;
                }
                break;
            }
            case 0x0c:
            case 0x0d: {
                // Bit pattern 110x, so there is one additional byte.
                u1 byte2 = *(data++);
                if ((byte2 & 0xc0) != 0x80) {
                    fprintf(stderr, "Illegal continuation byte %#x", byte2);
                    return NULL;
                }
                u2 value = ((byte1 & 0x1f) << 6) | (byte2 & 0x3f);
                if ((value != 0) && (value < 0x80)) {
                    fprintf(stderr, "Illegal representation for value %x", value);
                    return NULL;
                }
                break;
            }
        }
    }

    if (*(data++) != '\0') {
        fprintf(stderr, "String longer than indicated utf16_size %#x", utf16Size);
        return NULL;
    }

    return (void*) data;
}

static void* intraVerifyDebugInfoItem(const CheckState* state, void* ptr) {
    const u1* fileEnd = state->fileEnd;
    const u1* data = (const u1*) ptr;
    bool okay = true;
    u4 i;

    readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);

    if (!okay) {
        fprintf(stderr, "Bogus line_start");
        return NULL;
    }

    u4 parametersSize =
        readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);

    if (!okay) {
        fprintf(stderr, "Bogus parameters_size");
        return NULL;
    }

    if (parametersSize > 65536) {
        fprintf(stderr, "Invalid parameters_size: %#x", parametersSize);
        return NULL;
    }

    for (i = 0; i < parametersSize; i++) {
        u4 parameterName =
            readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);

        if (!okay) {
            fprintf(stderr, "Bogus parameter_name");
            return NULL;
        }

        if (parameterName != 0) {
            parameterName--;
            CHECK_INDEX(parameterName, state->pHeader->stringIdsSize);
        }
    }

    bool done = false;
    while (!done) {
        u1 opcode = *(data++);

        switch (opcode) {
            case DBG_END_SEQUENCE: {
                done = true;
                break;
            }
            case DBG_ADVANCE_PC: {
                readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                break;
            }
            case DBG_ADVANCE_LINE: {
                readAndVerifySignedLeb128(&data, fileEnd, &okay);
                break;
            }
            case DBG_START_LOCAL: {
                u4 idx;
                u4 regNum = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (regNum >= 65536) {
                    okay = false;
                    break;
                }
                idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (idx != 0) {
                    idx--;
                    CHECK_INDEX(idx, state->pHeader->stringIdsSize);
                }
                idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (idx != 0) {
                    idx--;
                    CHECK_INDEX(idx, state->pHeader->stringIdsSize);
                }
                break;
            }
            case DBG_END_LOCAL:
            case DBG_RESTART_LOCAL: {
                u4 regNum = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (regNum >= 65536) {
                    okay = false;
                    break;
                }
                break;
            }
            case DBG_START_LOCAL_EXTENDED: {
                u4 idx;
                u4 regNum = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (regNum >= 65536) {
                    okay = false;
                    break;
                }
                idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (idx != 0) {
                    idx--;
                    CHECK_INDEX(idx, state->pHeader->stringIdsSize);
                }
                idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (idx != 0) {
                    idx--;
                    CHECK_INDEX(idx, state->pHeader->stringIdsSize);
                }
                idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (idx != 0) {
                    idx--;
                    CHECK_INDEX(idx, state->pHeader->stringIdsSize);
                }
                break;
            }
            case DBG_SET_FILE: {
                u4 idx = readAndVerifyUnsignedLeb128(&data, fileEnd, &okay);
                if (!okay) break;
                if (idx != 0) {
                    idx--;
                    CHECK_INDEX(idx, state->pHeader->stringIdsSize);
                }
                break;
            }
            default: {
                // No arguments to parse for anything else.
            }
        }

        if (!okay) {
            fprintf(stderr, "Bogus syntax for opcode %02x", opcode);
            return NULL;
        }
    }

    return (void*) data;
}

static void* intraVerifyAnnotationItem(const CheckState* state, void* ptr) {
    const u1* data = (const u1*) ptr;

    CHECK_PTR_RANGE(data, data + 1);

    switch (*(data++)) {
        case kDexVisibilityBuild:
        case kDexVisibilityRuntime:
        case kDexVisibilitySystem: {
            break;
        }
        default: {
            fprintf(stderr, "Bogus annotation visibility: %#x", *data);
            return NULL;
        }
    }

    return (void*) verifyEncodedAnnotation(state, data, false);
}

static void* intraVerifyEncodedArrayItem(const CheckState* state, void* ptr) {
    return (void*) verifyEncodedArray(state, (const u1*) ptr, false);
}

static bool swapEverythingButHeaderAndMap(CheckState* state,
        DexMapList* pMap) {
    const DexMapItem* item = pMap->list;
    u4 lastOffset = 0;
    u4 count = pMap->size;
    bool okay = true;

    while (okay && count--) {
        u4 sectionOffset = item->offset;
        u4 sectionCount = item->size;
        u2 type = item->type;

        if (lastOffset < sectionOffset) {
            CHECK_OFFSET_RANGE(lastOffset, sectionOffset);
            const u1* ptr = (const u1*) filePointer(state, lastOffset);
            while (lastOffset < sectionOffset) {
                if (*ptr != '\0') {
                    fprintf(stderr, "Non-zero padding 0x%02x before section start @ %x",
                            *ptr, lastOffset);
                    okay = false;
                    break;
                }
                ptr++;
                lastOffset++;
            }
        } else if (lastOffset > sectionOffset) {
            fprintf(stderr, "Section overlap or out-of-order map: %x, %x",
                    lastOffset, sectionOffset);
            okay = false;
        }

        if (!okay) {
            break;
        }

        switch (type) {
            case kDexTypeHeaderItem: {
                /*
                 * The header got swapped very early on, but do some
                 * additional sanity checking here.
                 */
                okay = checkHeaderSection(state, sectionOffset, sectionCount,
                        &lastOffset);
                break;
            }
            case kDexTypeStringIdItem: {
                okay = checkBoundsAndIterateSection(state, sectionOffset,
                        sectionCount, state->pHeader->stringIdsOff,
                        state->pHeader->stringIdsSize, swapStringIdItem,
                        sizeof(u4), &lastOffset);
                break;
            }
            case kDexTypeTypeIdItem: {
                okay = checkBoundsAndIterateSection(state, sectionOffset,
                        sectionCount, state->pHeader->typeIdsOff,
                        state->pHeader->typeIdsSize, swapTypeIdItem,
                        sizeof(u4), &lastOffset);
                break;
            }
            case kDexTypeProtoIdItem: {
                okay = checkBoundsAndIterateSection(state, sectionOffset,
                        sectionCount, state->pHeader->protoIdsOff,
                        state->pHeader->protoIdsSize, swapProtoIdItem,
                        sizeof(u4), &lastOffset);
                break;
            }
            case kDexTypeFieldIdItem: {
                okay = checkBoundsAndIterateSection(state, sectionOffset,
                        sectionCount, state->pHeader->fieldIdsOff,
                        state->pHeader->fieldIdsSize, swapFieldIdItem,
                        sizeof(u4), &lastOffset);
                break;
            }
            case kDexTypeMethodIdItem: {
                okay = checkBoundsAndIterateSection(state, sectionOffset,
                        sectionCount, state->pHeader->methodIdsOff,
                        state->pHeader->methodIdsSize, swapMethodIdItem,
                        sizeof(u4), &lastOffset);
                break;
            }
            case kDexTypeClassDefItem: {
                okay = checkBoundsAndIterateSection(state, sectionOffset,
                        sectionCount, state->pHeader->classDefsOff,
                        state->pHeader->classDefsSize, swapClassDefItem,
                        sizeof(u4), &lastOffset);
                break;
            }
            case kDexTypeMapList: {
                /*
                 * The map section was swapped early on, but do some
                 * additional sanity checking here.
                 */
                okay = checkMapSection(state, sectionOffset, sectionCount,
                        &lastOffset);
                break;
            }
            case kDexTypeTypeList: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        swapTypeList, sizeof(u4), &lastOffset, type);
                break;
            }
            case kDexTypeAnnotationSetRefList: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        swapAnnotationSetRefList, sizeof(u4), &lastOffset,
                        type);
                break;
            }
            case kDexTypeAnnotationSetItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        swapAnnotationSetItem, sizeof(u4), &lastOffset, type);
                break;
            }
            case kDexTypeClassDataItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        intraVerifyClassDataItem, sizeof(u1), &lastOffset,
                        type);
                break;
            }
            case kDexTypeCodeItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        swapCodeItem, sizeof(u4), &lastOffset, type);
                break;
            }
            case kDexTypeStringDataItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        intraVerifyStringDataItem, sizeof(u1), &lastOffset,
                        type);
                break;
            }
            case kDexTypeDebugInfoItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        intraVerifyDebugInfoItem, sizeof(u1), &lastOffset,
                        type);
                break;
            }
            case kDexTypeAnnotationItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        intraVerifyAnnotationItem, sizeof(u1), &lastOffset,
                        type);
                break;
            }
            case kDexTypeEncodedArrayItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        intraVerifyEncodedArrayItem, sizeof(u1), &lastOffset,
                        type);
                break;
            }
            case kDexTypeAnnotationsDirectoryItem: {
                okay = iterateDataSection(state, sectionOffset, sectionCount,
                        swapAnnotationsDirectoryItem, sizeof(u4), &lastOffset,
                        type);
                break;
            }
            default: {
                fprintf(stderr, "Unknown map item type %04x", type);
                return false;
            }
        }

        if (!okay) {
            fprintf(stderr, "Swap of section type %04x failed", type);
        }

        item++;
    }

    return okay;
}

bool dexDataMapVerify0Ok(DexDataMap* map, u4 offset, u2 type) {
    if (offset == 0) {
        return true;
    }

    return dexDataMapVerify(map, offset, type);
}

static u4 findFirstClassDataDefiner(const CheckState* state,
        DexClassData* classData) {
    if (classData->header.staticFieldsSize != 0) {
        u4 fieldIdx = classData->staticFields[0].fieldIdx;
        const DexFieldId* field = dexGetFieldId(state->pDexFile, fieldIdx);
        return field->classIdx;
    }

    if (classData->header.instanceFieldsSize != 0) {
        u4 fieldIdx = classData->instanceFields[0].fieldIdx;
        const DexFieldId* field = dexGetFieldId(state->pDexFile, fieldIdx);
        return field->classIdx;
    }

    if (classData->header.directMethodsSize != 0) {
        u4 methodIdx = classData->directMethods[0].methodIdx;
        const DexMethodId* meth = dexGetMethodId(state->pDexFile, methodIdx);
        return meth->classIdx;
    }

    if (classData->header.virtualMethodsSize != 0) {
        u4 methodIdx = classData->virtualMethods[0].methodIdx;
        const DexMethodId* meth = dexGetMethodId(state->pDexFile, methodIdx);
        return meth->classIdx;
    }

    return kDexNoIndex;
}

static u4 findFirstAnnotationsDirectoryDefiner(const CheckState* state,
        const DexAnnotationsDirectoryItem* dir) {
    if (dir->fieldsSize != 0) {
        const DexFieldAnnotationsItem* fields =
            dexGetFieldAnnotations(state->pDexFile, dir);
        const DexFieldId* field =
            dexGetFieldId(state->pDexFile, fields[0].fieldIdx);
        return field->classIdx;
    }

    if (dir->methodsSize != 0) {
        const DexMethodAnnotationsItem* methods =
            dexGetMethodAnnotations(state->pDexFile, dir);
        const DexMethodId* method =
            dexGetMethodId(state->pDexFile, methods[0].methodIdx);
        return method->classIdx;
    }

    if (dir->parametersSize != 0) {
        const DexParameterAnnotationsItem* parameters =
            dexGetParameterAnnotations(state->pDexFile, dir);
        const DexMethodId* method =
            dexGetMethodId(state->pDexFile, parameters[0].methodIdx);
        return method->classIdx;
    }

    return kDexNoIndex;
}

static bool verifyClassDataIsForDef(const CheckState* state, u4 offset,
        u4 definerIdx) {
    if (offset == 0) {
        return true;
    }

    const u1* data = (const u1*) filePointer(state, offset);
    DexClassData* classData = dexReadAndVerifyClassData(&data, NULL);

    if (classData == NULL) {
        // Shouldn't happen, but bail here just in case.
        return false;
    }

    /*
     * The class_data_item verification ensures that
     * it consistently refers to the same definer, so all we need to
     * do is check the first one.
     */
    u4 dataDefiner = findFirstClassDataDefiner(state, classData);
    bool result = (dataDefiner == definerIdx) || (dataDefiner == kDexNoIndex);

    free(classData);
    return result;
}

static bool verifyAnnotationsDirectoryIsForDef(const CheckState* state,
        u4 offset, u4 definerIdx) {
    if (offset == 0) {
        return true;
    }

    const DexAnnotationsDirectoryItem* dir =
        (const DexAnnotationsDirectoryItem*) filePointer(state, offset);
    u4 annoDefiner = findFirstAnnotationsDirectoryDefiner(state, dir);

    return (annoDefiner == definerIdx) || (annoDefiner == kDexNoIndex);
}

static void* crossVerifyClassDefItem(const CheckState* state, void* ptr) {
    const DexClassDef* item = (const DexClassDef*) ptr;
    u4 classIdx = item->classIdx;
    const char* descriptor = dexStringByTypeIdx(state->pDexFile, classIdx);

    if (!dexIsClassDescriptor(descriptor)) {
        fprintf(stderr, "Invalid class: '%s'", descriptor);
        return NULL;
    }

    if (setDefinedClassBit(state, classIdx)) {
        fprintf(stderr, "Duplicate class definition: '%s'", descriptor);
        return NULL;
    }

    bool okay =
        dexDataMapVerify0Ok(state->pDataMap,
                item->interfacesOff, kDexTypeTypeList)
        && dexDataMapVerify0Ok(state->pDataMap,
                item->annotationsOff, kDexTypeAnnotationsDirectoryItem)
        && dexDataMapVerify0Ok(state->pDataMap,
                item->classDataOff, kDexTypeClassDataItem)
        && dexDataMapVerify0Ok(state->pDataMap,
                item->staticValuesOff, kDexTypeEncodedArrayItem);

    if (!okay) {
        return NULL;
    }

    if (item->superclassIdx != kDexNoIndex) {
        descriptor = dexStringByTypeIdx(state->pDexFile, item->superclassIdx);
        if (!dexIsClassDescriptor(descriptor)) {
            fprintf(stderr, "Invalid superclass: '%s'", descriptor);
            return NULL;
        }
    }

    const DexTypeList* interfaces =
        dexGetInterfacesList(state->pDexFile, item);
    if (interfaces != NULL) {
        u4 size = interfaces->size;
        u4 i;

        /*
         * Ensure that all interfaces refer to classes (not arrays or
         * primitives).
         */
        for (i = 0; i < size; i++) {
            descriptor = dexStringByTypeIdx(state->pDexFile,
                    dexTypeListGetIdx(interfaces, i));
            if (!dexIsClassDescriptor(descriptor)) {
                fprintf(stderr, "Invalid interface: '%s'", descriptor);
                return NULL;
            }
        }

        /*
         * Ensure that there are no duplicates. This is an O(N^2) test,
         * but in practice the number of interfaces implemented by any
         * given class is low. I will buy a milkshake for the
         * first person to show me a realistic case for which this test
         * would be unacceptably slow.
         */
        for (i = 1; i < size; i++) {
            u4 idx1 = dexTypeListGetIdx(interfaces, i);
            u4 j;
            for (j = 0; j < i; j++) {
                u4 idx2 = dexTypeListGetIdx(interfaces, j);
                if (idx1 == idx2) {
                    fprintf(stderr, "Duplicate interface: '%s'",
                            dexStringByTypeIdx(state->pDexFile, idx1));
                    return NULL;
                }
            }
        }
    }

    if (!verifyClassDataIsForDef(state, item->classDataOff, item->classIdx)) {
        fprintf(stderr, "Invalid class_data_item");
        return NULL;
    }

    if (!verifyAnnotationsDirectoryIsForDef(state, item->annotationsOff,
                    item->classIdx)) {
        fprintf(stderr, "Invalid annotations_directory_item");
        return NULL;
    }

    return (void*) (item + 1);
}

static void* crossVerifyAnnotationSetRefList(const CheckState* state,
        void* ptr) {
    const DexAnnotationSetRefList* list = (const DexAnnotationSetRefList*) ptr;
    const DexAnnotationSetRefItem* item = list->list;
    int count = list->size;

    while (count--) {
        if (!dexDataMapVerify0Ok(state->pDataMap,
                        item->annotationsOff, kDexTypeAnnotationSetItem)) {
            return NULL;
        }
        item++;
    }

    return (void*) item;
}

static u4 annotationItemTypeIdx(const DexAnnotationItem* item) {
    const u1* data = item->annotation;
    return readUnsignedLeb128(&data);
}

static void* crossVerifyAnnotationSetItem(const CheckState* state, void* ptr) {
    const DexAnnotationSetItem* set = (const DexAnnotationSetItem*) ptr;
    int count = set->size;
    u4 lastIdx = 0;
    bool first = true;
    int i;

    for (i = 0; i < count; i++) {
        if (!dexDataMapVerify0Ok(state->pDataMap,
                        dexGetAnnotationOff(set, i), kDexTypeAnnotationItem)) {
            return NULL;
        }

        const DexAnnotationItem* annotation =
            dexGetAnnotationItem(state->pDexFile, set, i);
        u4 idx = annotationItemTypeIdx(annotation);

        if (first) {
            first = false;
        } else if (lastIdx >= idx) {
            fprintf(stderr, "Out-of-order entry types: %#x then %#x",
                    lastIdx, idx);
            return NULL;
        }

        lastIdx = idx;
    }

    return (void*) (set->entries + count);
}

static bool verifyFieldDefiner(const CheckState* state, u4 definingClass,
        u4 fieldIdx) {
    const DexFieldId* field = dexGetFieldId(state->pDexFile, fieldIdx);
    return field->classIdx == definingClass;
}

static bool verifyMethodDefiner(const CheckState* state, u4 definingClass,
        u4 methodIdx) {
    const DexMethodId* meth = dexGetMethodId(state->pDexFile, methodIdx);
    return meth->classIdx == definingClass;
}

static void* crossVerifyClassDataItem(const CheckState* state, void* ptr) {
    const u1* data = (const u1*) ptr;
    DexClassData* classData = dexReadAndVerifyClassData(&data, state->fileEnd);
    u4 definingClass = findFirstClassDataDefiner(state, classData);
    bool okay = true;
    u4 i;

    for (i = classData->header.staticFieldsSize; okay && (i > 0); /*i*/) {
        i--;
        const DexField* field = &classData->staticFields[i];
        okay = verifyFieldDefiner(state, definingClass, field->fieldIdx);
    }

    for (i = classData->header.instanceFieldsSize; okay && (i > 0); /*i*/) {
        i--;
        const DexField* field = &classData->instanceFields[i];
        okay = verifyFieldDefiner(state, definingClass, field->fieldIdx);
    }

    for (i = classData->header.directMethodsSize; okay && (i > 0); /*i*/) {
        i--;
        const DexMethod* meth = &classData->directMethods[i];
        okay = dexDataMapVerify0Ok(state->pDataMap, meth->codeOff,
                kDexTypeCodeItem)
            && verifyMethodDefiner(state, definingClass, meth->methodIdx);
    }

    for (i = classData->header.virtualMethodsSize; okay && (i > 0); /*i*/) {
        i--;
        const DexMethod* meth = &classData->virtualMethods[i];
        okay = dexDataMapVerify0Ok(state->pDataMap, meth->codeOff,
                kDexTypeCodeItem)
            && verifyMethodDefiner(state, definingClass, meth->methodIdx);
    }

    free(classData);

    if (!okay) {
        return NULL;
    }

    return (void*) data;
}

static const u1* crossVerifyFieldAnnotations(const CheckState* state, u4 count,
        const u1* addr, u4 definingClass) {
    const DexFieldAnnotationsItem* item = (DexFieldAnnotationsItem*) addr;

    while (count--) {
        if (!verifyFieldDefiner(state, definingClass, item->fieldIdx)) {
            return NULL;
        }
        if (!dexDataMapVerify(state->pDataMap, item->annotationsOff,
                        kDexTypeAnnotationSetItem)) {
            return NULL;
        }
        item++;
    }

    return (const u1*) item;
}

static const u1* crossVerifyMethodAnnotations(const CheckState* state,
        u4 count, const u1* addr, u4 definingClass) {
    const DexMethodAnnotationsItem* item = (DexMethodAnnotationsItem*) addr;

    while (count--) {
        if (!verifyMethodDefiner(state, definingClass, item->methodIdx)) {
            return NULL;
        }
        if (!dexDataMapVerify(state->pDataMap, item->annotationsOff,
                        kDexTypeAnnotationSetItem)) {
            return NULL;
        }
        item++;
    }

    return (const u1*) item;
}

static const u1* crossVerifyParameterAnnotations(const CheckState* state,
        u4 count, const u1* addr, u4 definingClass) {
    const DexParameterAnnotationsItem* item =
        (DexParameterAnnotationsItem*) addr;

    while (count--) {
        if (!verifyMethodDefiner(state, definingClass, item->methodIdx)) {
            return NULL;
        }
        if (!dexDataMapVerify(state->pDataMap, item->annotationsOff,
                        kDexTypeAnnotationSetRefList)) {
            return NULL;
        }
        item++;
    }

    return (const u1*) item;
}

static void* crossVerifyAnnotationsDirectoryItem(const CheckState* state,
        void* ptr) {
    const DexAnnotationsDirectoryItem* item = (const DexAnnotationsDirectoryItem*) ptr;
    u4 definingClass = findFirstAnnotationsDirectoryDefiner(state, item);

    if (!dexDataMapVerify0Ok(state->pDataMap,
                    item->classAnnotationsOff, kDexTypeAnnotationSetItem)) {
        return NULL;
    }

    const u1* addr = (const u1*) (item + 1);

    if (item->fieldsSize != 0) {
        addr = crossVerifyFieldAnnotations(state, item->fieldsSize, addr,
                definingClass);
        if (addr == NULL) {
            return NULL;
        }
    }

    if (item->methodsSize != 0) {
        addr = crossVerifyMethodAnnotations(state, item->methodsSize, addr,
                definingClass);
        if (addr == NULL) {
            return NULL;
        }
    }

    if (item->parametersSize != 0) {
        addr = crossVerifyParameterAnnotations(state, item->parametersSize,
                addr, definingClass);
        if (addr == NULL) {
            return NULL;
        }
    }

    return (void*) addr;
}

static bool crossVerifyEverything(CheckState* state, DexMapList* pMap)
{
    const DexMapItem* item = pMap->list;
    u4 count = pMap->size;
    bool okay = true;

    while (okay && count--) {
        u4 sectionOffset = item->offset;
        u4 sectionCount = item->size;

        switch (item->type) {
            case kDexTypeHeaderItem:
            case kDexTypeMapList:
            case kDexTypeTypeList:
            case kDexTypeCodeItem:
            case kDexTypeStringDataItem:
            case kDexTypeDebugInfoItem:
            case kDexTypeAnnotationItem:
            case kDexTypeEncodedArrayItem: {
                // There is no need for cross-item verification for these.
                break;
            }
            case kDexTypeStringIdItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyStringIdItem, sizeof(u4), NULL);
                break;
            }
            case kDexTypeTypeIdItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyTypeIdItem, sizeof(u4), NULL);
                break;
            }
            case kDexTypeFieldIdItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyFieldIdItem, sizeof(u4), NULL);
                break;
            }
            case kDexTypeMethodIdItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyMethodIdItem, sizeof(u4), NULL);
                break;
            }
            case kDexTypeClassDefItem: {
                // Allocate (on the stack) the "observed class_def" bits.
                size_t arraySize = calcDefinedClassBitsSize(state);
                u4 definedClassBits[arraySize];
                memset(definedClassBits, 0, arraySize * sizeof(u4));
                state->pDefinedClassBits = definedClassBits;

                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyClassDefItem, sizeof(u4), NULL);

                state->pDefinedClassBits = NULL;
                break;
            }
            case kDexTypeAnnotationSetRefList: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyAnnotationSetRefList, sizeof(u4), NULL);
                break;
            }
            case kDexTypeAnnotationSetItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyAnnotationSetItem, sizeof(u4), NULL);
                break;
            }
            case kDexTypeClassDataItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyClassDataItem, sizeof(u1), NULL);
                break;
            }
            case kDexTypeAnnotationsDirectoryItem: {
                okay = iterateSection(state, sectionOffset, sectionCount,
                        crossVerifyAnnotationsDirectoryItem, sizeof(u4), NULL);
                break;
            }
            default: {
                fprintf(stderr, "Unknown map item type %04x", item->type);
                //return false;
                break;
            }
        }

        if (!okay) {
            fprintf(stderr, "Cross-item verify of section type %04x failed",
                    item->type);
        }

        item++;
    }

    return okay;
}

int dexSwapAndVerify(u1* addr, int len)
{
    DexHeader* pHeader;
    CheckState state;
    bool okay = true;

    memset(&state, 0, sizeof(state));
    printf("+++ swapping and verifying");

    /*
     * Note: The caller must have verified that "len" is at least as
     * large as a dex file header.
     */
    pHeader = (DexHeader*) addr;

    if (!dexHasValidMagic(pHeader)) {
        okay = false;
    }

    if (okay) {
        int expectedLen = (int) SWAP4(pHeader->fileSize);
        if (len < expectedLen) {
            fprintf(stderr, "ERROR: Bad length: expected %d, got %d", expectedLen, len);
            okay = false;
        } else if (len != expectedLen) {
            fprintf(stderr, "WARNING: Odd length: expected %d, got %d", expectedLen,
                    len);
            // keep going
        }
    }

    if (okay) {
        /*
         * Compute the adler32 checksum and compare it to what's stored in
         * the file.  This isn't free, but chances are good that we just
         * unpacked this from a jar file and have all of the pages sitting
         * in memory, so it's pretty quick.
         *
         * This might be a big-endian system, so we need to do this before
         * we byte-swap the header.
         */
        uLong adler = adler32(0L, Z_NULL, 0);
        const int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);
        u4 storedFileSize = SWAP4(pHeader->fileSize);
        u4 expectedChecksum = SWAP4(pHeader->checksum);

        adler = adler32(adler, ((const u1*) pHeader) + nonSum,
                    storedFileSize - nonSum);

        if (adler != expectedChecksum) {
            fprintf(stderr, "ERROR: bad checksum (%08lx, expected %08x)",
                adler, expectedChecksum);
            okay = false;
        }
    }

    if (okay) {
        state.fileStart = addr;
        state.fileEnd = addr + len;
        state.fileLen = len;
        state.pDexFile = NULL;
        state.pDataMap = NULL;
        state.pDefinedClassBits = NULL;
        state.previousItem = NULL;

        /*
         * Swap the header and check the contents.
         */
        okay = swapDexHeader(&state, pHeader);
    }

    if (okay) {
        state.pHeader = pHeader;

        if (pHeader->headerSize < sizeof(DexHeader)) {
            fprintf(stderr, "ERROR: Small header size %d, struct %d",
                    pHeader->headerSize, (int) sizeof(DexHeader));
            okay = false;
        } else if (pHeader->headerSize > sizeof(DexHeader)) {
            fprintf(stderr, "WARNING: Large header size %d, struct %d",
                    pHeader->headerSize, (int) sizeof(DexHeader));
            // keep going?
        }
    }

    if (okay) {
        /*
         * Look for the map. Swap it and then use it to find and swap
         * everything else.
         */
        if (pHeader->mapOff != 0) {
            DexFile dexFile;
            DexMapList* pDexMap = (DexMapList*) (addr + pHeader->mapOff);

            okay = okay && swapMap(&state, pDexMap);
            okay = okay && swapEverythingButHeaderAndMap(&state, pDexMap);

            dexFileSetupBasicPointers(&dexFile, addr);
            state.pDexFile = &dexFile;

            okay = okay && crossVerifyEverything(&state, pDexMap);
        } else {
            fprintf(stderr, "ERROR: No map found; impossible to byte-swap and verify");
            okay = false;
        }
    }

    if (!okay) {
        fprintf(stderr, "ERROR: Byte swap + verify failed");
    }

    if (state.pDataMap != NULL) {
        free(state.pDataMap);
    }

    return !okay;       // 0 == success
}

int dexSwapAndVerifyIfNecessary(u1* addr, int len)
{
    if (memcmp(addr, DEX_OPT_MAGIC, 4) == 0) {
        // It is an optimized dex file.
        return 0;
    }

    if (memcmp(addr, DEX_MAGIC, 4) == 0) {
        // It is an unoptimized dex file.
        //return dexSwapAndVerify(addr, len);
        return 0;
    }

    fprintf(stderr, "ERROR: Bad magic number (0x%02x %02x %02x %02x)",
             addr[0], addr[1], addr[2], addr[3]);

    return 1;
}

#if __BYTE_ORDER == __LITTLE_ENDIAN
#define X_LITTLE_ENDIAN
#endif


#define rol(value,bits) \
 (((value)<<(bits))|((value)>>(32-(bits))))

#ifdef X_LITTLE_ENDIAN
#define blk0(i) (block->l[i]=(rol(block->l[i],24)&0xFF00FF00) \
    |(rol(block->l[i],8)&0x00FF00FF))
#else
#define blk0(i) block->l[i]
#endif

#define blk(i) (block->l[i&15] = rol(block->l[(i+13)&15]^block->l[(i+8)&15] \
    ^block->l[(i+2)&15]^block->l[i&15],1))

/* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
#define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5);w=rol(w,30);
#define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5);w=rol(w,30);
#define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5);w=rol(w,30);
#define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5);w=rol(w,30);
#define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5);w=rol(w,30);


void SHA1Init(SHA1_CTX* context)
{
    /* SHA1 initialization constants */
    context->state[0] = 0x67452301;
    context->state[1] = 0xEFCDAB89;
    context->state[2] = 0x98BADCFE;
    context->state[3] = 0x10325476;
    context->state[4] = 0xC3D2E1F0;
    context->count[0] = context->count[1] = 0;
}

static void SHA1Transform(unsigned long state[5],
    const unsigned char buffer[64])
{
unsigned long a, b, c, d, e;
union CHAR64LONG16 {
    unsigned char c[64];
    unsigned long l[16];
};
CHAR64LONG16* block;
#ifdef SHA1HANDSOFF
static unsigned char workspace[64];
    block = (CHAR64LONG16*)workspace;
    memcpy(block, buffer, 64);
#else
    block = (CHAR64LONG16*)buffer;
#endif
    /* Copy context->state[] to working vars */
    a = state[0];
    b = state[1];
    c = state[2];
    d = state[3];
    e = state[4];
    /* 4 rounds of 20 operations each. Loop unrolled. */
    R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2);
    R0(c,d,e,a,b, 3); R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5);
    R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7); R0(c,d,e,a,b, 8);
    R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
    R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14);
    R0(a,b,c,d,e,15); R1(e,a,b,c,d,16); R1(d,e,a,b,c,17);
    R1(c,d,e,a,b,18); R1(b,c,d,e,a,19); R2(a,b,c,d,e,20);
    R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23);
    R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26);
    R2(d,e,a,b,c,27); R2(c,d,e,a,b,28); R2(b,c,d,e,a,29);
    R2(a,b,c,d,e,30); R2(e,a,b,c,d,31); R2(d,e,a,b,c,32);
    R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35);
    R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38);
    R2(b,c,d,e,a,39); R3(a,b,c,d,e,40); R3(e,a,b,c,d,41);
    R3(d,e,a,b,c,42); R3(c,d,e,a,b,43); R3(b,c,d,e,a,44);
    R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
    R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50);
    R3(e,a,b,c,d,51); R3(d,e,a,b,c,52); R3(c,d,e,a,b,53);
    R3(b,c,d,e,a,54); R3(a,b,c,d,e,55); R3(e,a,b,c,d,56);
    R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
    R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62);
    R4(c,d,e,a,b,63); R4(b,c,d,e,a,64); R4(a,b,c,d,e,65);
    R4(e,a,b,c,d,66); R4(d,e,a,b,c,67); R4(c,d,e,a,b,68);
    R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
    R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74);
    R4(a,b,c,d,e,75); R4(e,a,b,c,d,76); R4(d,e,a,b,c,77);
    R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);

    /* Add the working vars back into context.state[] */
    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;
    state[4] += e;
    /* Wipe variables */
/*    a = b = c = d = e = 0; Nice try, but the compiler
optimizes this out, anyway, and it produces an annoying
warning. */
}

void SHA1Update(SHA1_CTX* context, const unsigned char* data,
    unsigned long len)  /* JHB */
{
    unsigned long i, j; /* JHB */

    j = (context->count[0] >> 3) & 63;
    if ((context->count[0] += len << 3) < (len << 3))
        context->count[1]++;
    context->count[1] += (len >> 29);
    if ((j + len) > 63)
    {
        memcpy(&context->buffer[j], data, (i = 64-j));
        SHA1Transform(context->state, context->buffer);
        for ( ; i + 63 < len; i += 64) {
            SHA1Transform(context->state, &data[i]);
        }
        j = 0;
    }
    else
        i = 0;
    memcpy(&context->buffer[j], &data[i], len - i);
}

void SHA1Final(unsigned char digest[HASHSIZE], SHA1_CTX*
context)
{
unsigned long i;    /* JHB */
unsigned char finalcount[8];

    for (i = 0; i < 8; i++)
    {
        finalcount[i] = (unsigned char)((context->count[(i>=4?
            0:1)]>>((3-(i&3))*8))&255);
        /* Endian independent */
    }
    SHA1Update(context, (unsigned char *)"\200", 1);
    while ((context->count[0] & 504) != 448) {
        SHA1Update(context, (unsigned char *)"\0", 1);
    }
    SHA1Update(context, finalcount, 8);
    /* Should cause a SHA1Transform() */
    for (i = 0; i < HASHSIZE; i++) {
        digest[i] = (unsigned char)
         ((context->state[i>>2] >> ((3-(i & 3)) * 8) ) & 255);
    }
    /* Wipe variables */
    memset(context->buffer, 0, 64);
    memset(context->state, 0, HASHSIZE);
    memset(context->count, 0, 8);
    memset(&finalcount, 0, 8);
#ifdef SHA1HANDSOFF
    /* make SHA1Transform overwrite it's own static vars */
    SHA1Transform(context->state, context->buffer);
#endif
}


static void dexComputeSHA1Digest(const unsigned char* data, size_t length,
    unsigned char digest[])
{
    SHA1_CTX context;
    SHA1Init(&context);
    SHA1Update(&context, data, length);
    SHA1Final(digest, &context);
}

static const char* dexSHA1DigestToStr(const unsigned char digest[],char* tmpBuf)
{
    static const char hexDigit[] = "0123456789abcdef";
    char* cp;
    int i;

    cp = tmpBuf;
    for (i = 0; i < kSHA1DigestLen; i++) {
        *cp++ = hexDigit[digest[i] >> 4];
        *cp++ = hexDigit[digest[i] & 0x0f];
    }
    *cp++ = '\0';

    assert(cp == tmpBuf + kSHA1DigestOutputLen);

    return tmpBuf;
}

void processDexFile(DexFile* pDexFile, node* classes, int fp)
{
    int i;

    for (i = 0; i < (int) pDexFile->pHeader->classDefsSize; i++) {
		const DexClassDef* pClassDef;
		DexClassData* pClassData = NULL;
		const u1* pEncodedData;
		const char* classDescriptor;
		bool modify = false;
		
		pClassDef = dexGetClassDef(pDexFile, i);
		
		classDescriptor = dexStringByTypeIdx(pDexFile, pClassDef->classIdx);

		char* className = NULL;
		className = descriptorToDot(classDescriptor);

		struct node* temp;
		temp = classlist;
	
		while(temp != NULL) {
			char* cur_name = temp->classname;
			if(strcmp(cur_name, className) != 0)
				temp = temp->nextnode;
			else {
				modify = true;
				break;
			}
		}

		if(modify == true) {
			pEncodedData = dexGetClassData(pDexFile, pClassDef);
    		pClassData = dexReadAndVerifyClassData(&pEncodedData, NULL);
			for (int i = 0; i < (int) pClassData->header.directMethodsSize; i++) {
				const DexCode* pCode = dexGetCode(pDexFile, &pClassData->directMethods[i]);
				const u2* insns;
				int insnIdx;
				insns = pCode->insns;
				insnIdx = 0;
				while (insnIdx < (int) pCode->insnsSize) {
					u2* i = (u2*)insns;
					*i ^= (0xffff);
					insns += 1;
					insnIdx += 1;
				}
				insns = pCode->insns;
				
				lseek(fp, pClassData->directMethods[i].codeOff + sizeof(pCode->registersSize)
					+ sizeof(pCode->insSize) + sizeof(pCode->outsSize) + sizeof(pCode->triesSize)
					+ sizeof(pCode->debugInfoOff) + sizeof(pCode->insnsSize), SEEK_SET);
				write(fp, (u1*)insns, pCode->insnsSize*2);
			}	
			for (int i = 0; i < (int) pClassData->header.virtualMethodsSize; i++) {
				const DexCode* pCode = dexGetCode(pDexFile, &pClassData->virtualMethods[i]);
				const u2* insns;
				int insnIdx;
				insns = pCode->insns;
				insnIdx = 0;
				while (insnIdx < (int) pCode->insnsSize) {
					u2* i = (u2*)insns;
					*i ^= (0xffff);
					insns += 1;
					insnIdx += 1;
				}
				insns = pCode->insns;
				lseek(fp, pClassData->virtualMethods[i].codeOff + sizeof(pCode->registersSize)
					+ sizeof(pCode->insSize) + sizeof(pCode->outsSize) + sizeof(pCode->triesSize)
					+ sizeof(pCode->debugInfoOff) + sizeof(pCode->insnsSize), SEEK_SET);
				write(fp, (u1*)insns, pCode->insnsSize*2);
			}
			modifyNum++;
			modify = false;
		}

		free(pClassData);
    }
	// calculate the SHA1
	const DexHeader* pHeader = pDexFile->pHeader;
	unsigned char sha1Digest[kSHA1DigestLen];
    int nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum) + kSHA1DigestLen;
	dexComputeSHA1Digest(pDexFile->baseAddr + nonSum, pHeader->fileSize - nonSum, sha1Digest);
	memcpy((u1*)pHeader->signature, sha1Digest, kSHA1DigestLen);
	lseek(fp, 12, SEEK_SET);
	write(fp, (u1*)&pHeader->signature, 20);
	printf("modify the SHA1\n");
	
	// calculate the checksum
	uLong adler = adler32(0L, Z_NULL, 0);
    nonSum = sizeof(pHeader->magic) + sizeof(pHeader->checksum);
    u4 storedFileSize = SWAP4(pHeader->fileSize);

    adler = adler32(adler, ((const u1*) pHeader) + nonSum,
                storedFileSize - nonSum);
	u1* checksum = (u1*)&adler;
	lseek(fp, 8, SEEK_SET);
	write(fp, checksum, 4);
}

int process(const char* fileName)
{
	int len = strlen(fileName);
	if (len < 5) {
		fprintf(stderr, "dexfile name must end in .dex\n");
	}
	
	if (strcasecmp(fileName + len -3, "dex") != 0) {
		fprintf(stderr, "dexfile name must end in .dex\n");
	}

	len = strlen(gOptions.inputfile);
	if (len < 5) {
		fprintf(stderr, "inputfile name must end in .txt\n");
	}

	len = strlen(gOptions.outputfile);
	if (len < 5) {
		fprintf(stderr, "outputfile name must end in .dex\n");
	}
	
	// process the inputfile to get the classes need to be modified
	FILE* fp = NULL;
	fp = fopen(gOptions.inputfile, "r");
	char ch;
	char src[2];
	src[1] = '\0';
	
	if(fp == NULL) {
		fprintf(stderr, "the inputfile open failed.\n");
	}
	else {
		node* classnode = new node();
		memset(classnode->classname, '\0', BUF);
		classnode->nextnode = NULL;

		// the classes info are saved in the classlist linked list
		classlist = classnode;
		current = classnode;
		
		do {
			ch = fgetc(fp);
			if (ch == '\r') {
				ch = fgetc(fp);
			}
			if (ch == '\n') {
				node* anode = new node();
				memset(anode->classname, '\0', BUF);
				anode->nextnode = NULL;
				
				current->nextnode = anode;
				current = anode;
				while (ch == '\n')
					ch = fgetc(fp);
			}
			if (!feof(fp)) {
				src[0] = ch;
				strcat(current->classname, src);
			}
 		} while (!feof(fp));

		// the source .dex
		int fdex = -1;
		fdex = open(fileName, O_RDONLY | O_BINARY);
		// the dest .dex
		int fmd = -1;
		fmd = open(gOptions.outputfile, O_RDWR | O_BINARY | O_CREAT, S_IWUSR);
		
		if(fdex < 0) {
			fprintf(stderr, "the source dexfile open failed.\n");
			goto bail;
		}
		else if(fmd < 0) {
			fprintf(stderr, "the destination dexfile open failed.\n");
			goto bail;
		}
		else {
			off_t start;
    		size_t length;
			void* memPtr;
			char* buff;
			MemMapping map;

			//copy the .dex
			int bytes_read;
			int bytes_write;
			char* ptr;
			//char buffer[BUF];
			
			if (getFileStartAndLength(fdex, &start, &length) < 0)
        		return -1;
			memPtr = malloc(length);
			
			if (read(fdex, memPtr, length) < 0) {
        		fprintf(stderr, "read file failed.\n");
        		return -1;
    		}

			map.baseAddr = map.addr = memPtr;
    		map.baseLength = map.length = length;

			if (write(fmd, memPtr, length) < 0) {
        		fprintf(stderr, "write file failed.\n");
        		return -1;
    		}
			
			if (dexSwapAndVerifyIfNecessary((u1*) map.addr, map.length)) {
        		fprintf(stderr, "ERROR: Failed structural verification of '%s'\n", gOptions.outputfile);
        		goto bail;
    		}
			
			// process the .dex
			DexFile* pDexFile = NULL;
			int flags = kDexParseVerifyChecksum;
			
			pDexFile = dexFileParse((u1*)map.addr, map.length, flags);
			if (pDexFile == NULL) {
        		fprintf(stderr, "ERROR: DEX parse failed\n");
        		goto bail;
   	 		}

			modifyNum = 0;
			processDexFile(pDexFile, classlist, fmd);
			printf("the number of modified classes: %d\n", modifyNum);
		}
bail:
		current = classlist;
		while(current->nextnode != NULL) {
			classlist = current;
			current = current->nextnode;
			delete classlist;
		}
		delete current;
		classlist = NULL;
		current = NULL;

		if(fmd >= 0)
			close(fmd);
		
		if(fdex >= 0)
			close(fdex);
		
		fclose(fp);
		fp = NULL;

		return 0;
	}
}

void usage(void){
	fprintf(stderr, "modify the dex file\n\n");
	fprintf(stderr, "modify_dex: -i inputfile -o outputfile dexfile...\n");
	fprintf(stderr, "\n");
	fprintf(stderr, " -i : inputfile name (list the classes you want to modified)\n");
	fprintf(stderr, " -o : outputfile name \n");
}

int main(int argc, char* const argv[])
{
	int ic;
	bool wantUsage = false;

	memset(&gOptions, 0, sizeof(gOptions));

	while(1){
		ic = getopt(argc, argv, "i:o:");
		if (ic < 0)
			break;
		
		switch (ic) {
		case 'i':
			gOptions.inputfile = optarg;
			break;
		case 'o':
			gOptions.outputfile = optarg;
			break;
		default:
			wantUsage = true;
			break;
		}
	}

	if (optind == argc) {
		fprintf(stderr, "no dexfile specified.\n");
		wantUsage = true;
	}

	if(gOptions.inputfile == 0) {
		fprintf(stderr, "no inputfile.\n");
		wantUsage = true;
	}

	if(gOptions.outputfile == 0) {
		fprintf(stderr, "no outputfile.\n");
		wantUsage = true;
	}

	if(wantUsage) {
		usage();
		return 2;
	}

	process(argv[optind]);

	return 0;
}
